Какие существуют распространённые трюки битовой манипуляции?

Question

Accepted Answer

**Битовая манипуляция** работает непосредственно с двоичным представлением целых чисел, используя операции AND, OR, XOR, NOT и сдвиги. Она позволяет создавать компактный, безветвлющийся и очень быстрый код. ## Основные операции ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## Полезные трюки ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## Пример: найти одиночное число (трюк с XOR) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Сложность Битовые операции выполняются за O(1); сканирование с XOR выше работает за **O(n) по времени, O(1) по памяти**. ## Когда использовать / подводные камни Используйте для **битовых масок** (перечисление подмножеств, DP по состояниям), флагов, быстрых математических вычислений и низкоуровневого/встроенного кода. Остерегайтесь знаковых битов, зависящего от языка поведения сдвигов и читаемости — комментируйте неочевидные трюки. ## Почему это важно Битовая манипуляция даёт элегантные решения за O(1) памяти (как трюк с одиночным числом через XOR), которые производят впечатление на собеседованиях. Bitmask DP делает многие задачи комбинаторного пространства состояний разрешимыми. Она критически важна в системном программировании, графике, сжатии данных и коде, критичном к производительности, где каждый цикл процессора на счету.