Сейчас пишу статью на wiki — конспекты про битовые операции, трюки и прочую битовую магию. Если вы знаете полезные трюки с битами, которые применяются в алгоритмах, а также просто прикольные вещи, то делитесь своими трюками в комментариях. Также приветствуются извращённые решения известных задач. Например: обменять значения переменных, не использую третью переменную с помощью XOR.
Приветствуются комментарии в виде:
- Описание задачи
- Решение задачи в виде кода, по-возможности короткое объяснение для не очевидных трюков.
Пример идеального комментария:
Является ли число степенью двойки?
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = v && !(v & (v - 1))
Короткое объяснение: Пусть v — это степень двойки (в двоичном представлении 1 единица и k нулей справа), тогда v — 1 в двоичном представлении это число, состоящее из k единиц. Очевидно, что побитовое И чисел
v и v — 1 должно давать в результате 0.
Задача для затравки: Найти младший единичный бит за O(1)
UPD: Интересные ссылки из комментов
