Двоичное представление и побитовые операции

Двоичное представление и базовые побитовые операции AND, OR, XOR, NOT и сдвиги — алфавит битовой математики.

Двоичная запись числа представляет его как сумму степеней двойки; побитовые операции работают с этими битами параллельно и очень быстро.

Зачем это в олимпиадах

Биты — это и способ ускорить решение в разы (битовые маски, сжатие состояний в динамике), и источник элегантных трюков (XOR находит «лишний» элемент за O(n) и O(1) памяти). Понимание двоичной системы и побитовых операций нужно для битмасок в ДП, для нима из прошлого раздела, для быстрых структур данных. Это фундаментальный навык: многие задачи, неподъёмные «в лоб», решаются за миллисекунды, если мыслить битами. Начнём с азов — представления чисел и пяти базовых операций.

Двоичное представление

Число в двоичной системе — сумма степеней двойки: 13 = 8 + 4 + 1 = 1101₂. Бит i (нумеруя с нуля справа) отвечает за 2i. В Python двоичный вид даёт bin(x), а число бит-единиц — bin(x).count('1') или x.bit_count(). Целые в Python длинные, поэтому биты не ограничены 32 или 64 — ещё одно удобство для битовых задач.

x = 13
print(bin(x))            # 0b1101
print(x.bit_length())    # сколько значащих бит: 4
print(x.bit_count())     # сколько единичных бит: 3

# собрать число из степеней двойки
print((1 << 3) + (1 << 2) + (1 << 0))   # 8+4+1 = 13

Вывод:

0b1101
4
3
13

AND, OR, XOR, NOT

Четыре логические операции применяются к каждой паре бит независимо:

a, b = 0b1100, 0b1010   # 12 и 10
print(bin(a & b))       # 0b1000 = 8  (общие биты)
print(bin(a | b))       # 0b1110 = 14 (объединение бит)
print(bin(a ^ b))       # 0b110  = 6  (различающиеся биты)
print(~a)               # -13: ~x == -(x+1) в дополнительном коде

Вывод:

0b1000
0b1110
0b110
-13

Обратите внимание на ~a = −13: в Python отрицательные числа представлены в «бесконечном» дополнительном коде, поэтому ~x = −(x+1). Когда нужна инверсия в пределах k бит, используют маску: a ^ ((1 << k) − 1). Об этом — в уроке про трюки.

Сдвиги

Сдвиг влево x << k приписывает k нулей справа — это умножение на 2k. Сдвиг вправо x >> k отбрасывает k младших бит — это целочисленное деление на 2k. Сдвиги — самый быстрый способ умножать и делить на степени двойки и строить «маску одного бита» 1 << i.

print(5 << 3)      # 5 * 2^3 = 40
print(40 >> 2)     # 40 // 4 = 10
print(1 << 10)     # 1024 — i-й бит как маска
print(bin(0b101 << 2))   # 0b10100 — приписали два нуля

Вывод:

40
10
1024
0b10100

Свойства XOR — почему он особенный

XOR заслуживает отдельного внимания: a ^ a = 0 (число гасит само себя), a ^ 0 = a (ноль нейтрален), операция коммутативна и ассоциативна (порядок не важен). Из этих свойств следует мощный факт: если XOR-ить все элементы, где каждый встречается дважды, кроме одного, парные элементы взаимно уничтожатся, и останется ровно одиночка. Это классический трюк «найти непарный элемент».

from functools import reduce

# Все числа встречаются дважды, кроме одного. Найти одиночку.
data = [4, 1, 2, 1, 2, 7, 4]
result = reduce(lambda a, b: a ^ b, data, 0)
print(result)           # 7 — пары взаимно уничтожились

# Проверим свойства XOR
print(5 ^ 5, 5 ^ 0)     # 0 и 5

Вывод:

7
0 5

Здесь 4^1^2^1^2^7^4: пары 4,4, 1,1, 2,2 обнуляются, остаётся 7. Алгоритм работает за один проход и O(1) дополнительной памяти — недостижимо для подходов на множествах или сортировке. Этот трюк мы разовьём в третьем уроке раздела.

Разбор задачи: пропущенное число и обмен без буфера

Два хрестоматийных XOR-трюка. Первый: в массиве лежат все числа от 0 до n, кроме одного — найти пропущенное. XOR всех индексов 0..n с XOR всех элементов: совпадающие значения сократятся, останется недостающее. Второй: обмен двух переменных без временной — три XOR. Оба работают за счёт a^a=0 и обратимости XOR.

def find_missing(nums, n):
    x = n                       # начнём с n (его нет среди индексов 0..n-1)
    for i, v in enumerate(nums):
        x ^= i ^ v              # XOR индекса и значения
    return x

print(find_missing([0, 1, 3, 4], 4))   # пропущено 2

# обмен без временной переменной
a, b = 5, 9
a ^= b
b ^= a       # теперь b = исходное a
a ^= b       # теперь a = исходное b
print(a, b)

Вывод:

2
9 5

Пропущенное число найдено: x накопил XOR всех индексов и значений, и всё, кроме недостающего 2, сократилось. Обмен через три XOR превратил (5, 9) в (9, 5) без буфера — каждый шаг обратим, поэтому значения «прокручиваются». Оба приёма — за O(1) памяти, и оба опираются на одно свойство: XOR сам себе обратен.

Перевод числа в двоичную запись вручную

Полезно понимать, как число превращается в биты «руками», а не через bin. Алгоритм — деление на 2 с выписыванием остатков снизу вверх: остаток от деления на 2 даёт младший бит, частное обрабатываем дальше. Это ровно то, что делает компьютер, и понимание механики помогает с битовыми трюками.

def to_binary(n):
    if n == 0:
        return "0"
    bits = ""
    while n > 0:
        bits = str(n & 1) + bits   # младший бит приписываем слева
        n >>= 1                     # делим на 2
    return bits

print(to_binary(13))      # 1101
print(to_binary(42))      # 101010
print(to_binary(13) == bin(13)[2:])   # совпадает с встроенным bin

Вывод:

1101
101010
True

Число 13 — это 1101 (то есть 8+4+1), а 42 — 101010. Каждый шаг выделяет младший бит через n & 1 и сдвигает число вправо n >> 1 — те самые операции из таблицы выше. Понимание этого цикла делает все последующие битовые приёмы прозрачными: они лишь по-разному комбинируют выделение бита и сдвиг.

Подводные камни

• Приоритет операций. В Python &, |, ^ имеют низкий приоритет — ниже сравнений! x & 1 == 0 читается как x & (1 == 0). Ставьте скобки: (x & 1) == 0.
• NOT и знак. ~x даёт отрицательное число; для инверсии в k битах используйте XOR с маской.
• XOR — это ^, не **. В Python ** — возведение в степень, частая путаница для пришедших из математики.
• Длинные целые. В Python нет переполнения битовых операций, но при переносе на C++ помните про разрядность типа.

Итог

• Число — сумма степеней двойки; bin, bit_length, bit_count помогают с битами.
• AND/OR/XOR/NOT работают побитово; сдвиги <</>> — умножение/деление на степени двойки.
• XOR: a^a=0, a^0=a, коммутативен и ассоциативен — находит непарный элемент за O(n), O(1).
• Скобки обязательны: приоритет битовых операций ниже сравнений.