Здравствуйте!
Задаю этот вопрос скорее для самообразования, чем из реальной сиюминутной необходимости:
Что нужно знать программистам "более высоких уровней" о побитовых операциях? О каких конкретных случаях их применения желательно знать в любом случае? Приведите примеры из вашей практики, когда использования побитовых операций существенно ускоряло/упрощало?/улучшало ваш код?
Что я уже знаю:
Я знаю о битовых масках
знаю, что "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, изобретать велосипед не стоит.
Ещё один важный частный случай — это реализация алгоритмов наподобие криптографических, которые сами оперируют с битовыми представлениями чисел. Здесь, конечно, без битовой арифметики не обойтись.
Комментариев нет:
Отправить комментарий