Какие битовые операции вы знаете и где они применяются?

Операции:

• a & b — бит 1, если он 1 в обоих (пересечение, маскирование);
• a | b — бит 1, если он 1 хотя бы в одном (объединение);
• a ^ b — бит 1, если биты различаются. Свойства: a ^ a = 0, a ^ 0 = a, операция обратима;
• ~a — инверсия всех бит; в дополнительном коде ~a = −a − 1;
• a << k — умножение на 2ᵏ, a >> k — деление на 2ᵏ с округлением вниз (для знаковых — арифметический сдвиг), в Java ещё >>> — логический.

Где применяют:

• флаги и права — набор булевых признаков в одном числе: права файла rwx в Unix (chmod 754), EnumSet в Java хранит множество как биты;
• маска вместо остатка — если ёмкость степень двойки, hash % n равно hash & (n − 1), а это быстрее деления. Поэтому HashMap держит размер степенью двойки, а перед маской перемешивает старшие биты хеша (h ^ (h >>> 16)), иначе младшие биты плохого хеша дали бы коллизии;
• приёмы — x & (x − 1) убирает младшую единицу (степень двойки, подсчёт единиц), x & −x оставляет только младшую единицу (дерево Фенвика), x >> 31 — знак;
• XOR — найти единственный непарный элемент массива за O(n) и O(1) памяти; чётность и RAID-5; простейшее шифрование «одноразовым блокнотом»;
• битовые множества и фильтры — BitSet, битовые карты в индексах баз, фильтр Блума;
• сети — маска подсети: ip & mask даёт адрес сети.

Порядок байтов (endianness) — отдельный вопрос: битовые операции работают со значением, а не с его раскладкой в памяти, поэтому от него не зависят.

READ, WRITE, EXEC = 4, 2, 1
perm = READ | WRITE          # 6
perm & EXEC != 0             # False — нет права на запуск
perm &= ~WRITE               # 4 — сняли запись

def is_pow2(x): return x > 0 and x & (x - 1) == 0

def single(nums):            # каждый встречается дважды, кроме одного
    r = 0
    for x in nums: r ^= x
    return r

single([4, 1, 2, 1, 2])      # 4