Страницы

Поиск по вопросам

понедельник, 1 октября 2018 г.

Побитовые операции - о каких из них полезно знать программистам “более высоких” уровней?

Здравствуйте!
Задаю этот вопрос скорее для самообразования, чем из реальной сиюминутной необходимости:
Что нужно знать программистам "более высоких уровней" о побитовых операциях? О каких конкретных случаях их применения желательно знать в любом случае? Приведите примеры из вашей практики, когда использования побитовых операций существенно ускоряло/упрощало?/улучшало ваш код?

Что я уже знаю:
Я знаю о битовых масках знаю, что "x & 1" проверяет чётность числа (например, здесь, ответ @avp) знаю про побитовые сдвиги и умножение/деление на степени двойки.
Также я прочитал все топики на эту тему здесь на ХэшКоде и основные на StackOverflow, нашёл вот этот интересный ресурс: Bit Twiddling Hacks
Также я наслышан об удивительном решении задачи нахождения Fast inverse square root
И наслышан о книге Hacker's Delight, которую пока что не читал. Она же на русском

В дополнение к вопросу напишу, что кроме битовых масок (которые я уже давно использую) из всего того, что мне встретилось, единственным более-менее полезным для себя и своей повседневной практики я нашёл лишь только проверку числа на чётность, что навело меня на мысль, что наверняка должны быть какие-то ещё диковинные случаи, когда использование битовых операций уместно и даже желательно.
И ещё напишу, что интересуюсь этим вопросом сугубо с практической стороны, поэтому скорее буду признателен за простые примеры и реальный опыт, чем за сухие ссылки на "6 том всемирного собрания алгоритмов из какого-нибудь Великого британского учебного учреждения" и всё в таком духе.
Спасибо))

Перечень интересных ссылок на смежные темы
Получение модуля числа без операции сравнения
Do bitwise operators (other than shifts) make any mathematical sense in base-10?


Ответ

Битовые операции обычно нужны лишь для экстремальной оптимизации. В обычных случаях можно обходиться без них. В обычных случаях битовые трюки затрудняют понимание кода, применяйте их только если они вам осознано необходимы. Учтите, что современные компиляторы довольно умны, и применяют битовые трюки самостоятельно. Многие программисты, к сожалению, злоупотребляют низкоуровневыми оптимизациями, что вредит качеству кода: код становится очень сложным в поддержке, хрупким, и подверженным тонким ошибкам.
С другой стороны, раз уж битовые операции так часто используются, стоит их знать, чтобы уметь корректно читать и понимать чужой код.
Для работы с упакованными значениями в C (и C++), например, обычно лучше использовать не сдвиги и маски, а битовые поля. О нужных величинах сдвига позаботится сам компилятор. В C (и кажется в C++) для выделения старшего и младшего полубайта лучше использовать такую структуру:
typedef union LH { char c; struct { char h:4; char l:4; }; } LH;
(учтите, стандарт не даёт гарантий правильности этого, так как, например, нет гарантий, что байт содержит в точности 8 бит).
Важный частный случай, в котором нужны битовые операции — массив бит (например, вы хотите использовать реально много булевых значений, и хотите пожертвовать скоростью ради выигрыша в размере структуры данных. Для этого вы можете завести большой массив char'ов, и адресовать в нём биты следующим образом:
// 8 бит на байт => делим на 8, чтобы получить номер бпйта inline char& Carrier(int n) { return payload[n >> 3]; }
// выделяем бит в байте: маска из трёх младших битов есть 0b111 = ((1 << 3) - 1) // 1 << x даёт число с одним взведённым битом inline int Bit(int n) { const int threeBitMask = (1 << 3) - 1); int bitNumber = n & threeBitMask; return 1 << bitNumber; }
inline bool GetBit(int n) { return Carrier(n) & Bit(n); }
inline void SetBit(int n, bool value) { if (value) Carrier(n) |= Bit(n); else Carrier(n) &= ~Bit(n); }
(не уверен на 100% в правильности кода). С другой стороны, это уже сделано один раз за нас, в C++ есть std::bitset, изобретать велосипед не стоит.
Ещё один важный частный случай — это реализация алгоритмов наподобие криптографических, которые сами оперируют с битовыми представлениями чисел. Здесь, конечно, без битовой арифметики не обойтись.

Комментариев нет:

Отправить комментарий