Задачи на быстрые вычисления – Учебник

6.4

О чём этот урок

Четыре фрагмента, которые встречаются в реальных программах. Прежде чем читать дальше, попробуйте сказать, что делает каждый:

if n & 1:
    ...

a ^= b
b ^= a
a ^= b

x & (x - 1) == 0

while x:
    x &= x - 1
    count += 1

Ничего сложного ни в одном из них нет: только побитовое И, исключающее ИЛИ и вычитание единицы. Но выглядят они как шифр – и в этом всё дело. Такие короткие устойчивые выражения называют идиомами: тот, кто их знает, читает запись целиком, как слово, а не разбирает по буквам.

В этом уроке: проверка чётности через x & 1 и остаток от деления на степень двойки через маску; что вычитание единицы делает с битами числа; идиомы x & (x - 1) и x & -x; проверка на степень двойки и типичная ошибка в ней; три способа посчитать единицы в числе; обмен двух переменных через XOR – и почему его не стоит писать; поиск непарного элемента за один проход.

Разминка. Прежде чем читать дальше, попробуйте сказать, что делает каждый из четырёх фрагментов выше. В конце урока сверимся.

Чётность: `x & 1`

Самая частая идиома из всех. Число чётно тогда и только тогда, когда его младший бит равен нулю – мы отмечали это ещё в уроке 6.1, теперь проговорим до конца.

Вспомните веса разрядов из урока 2.4: значение числа – это сумма битов, умноженных на веса 1, 2, 4, 8, 16… Все веса, кроме нулевого, чётные, значит и вклад их чётный при любых битах. Чётность всей суммы решает единственный разряд – нулевой.

x & 1 равно 1 у нечётных чисел и 0 у чётных.

Проверяем: 6 & 1 → 0, 7 & 1 → 1, 156 & 1 → 0.

Отдельно про отрицательные, потому что тут Python ведёт себя удобнее многих языков: -7 & 1 даёт 1, и -7 % 2 тоже даёт 1 – ответы совпадают. В C и Java -7 % 2 равно −1, и там & 1 и % 2 – уже разные проверки. Знакомая история: с приоритетом & и == из урока 6.1 было ровно так же.

А теперь обобщение, которое прямо следует из маски младших n битов (урок 6.3). Остаток от деления на степень двойки – это тоже маска:

x % (2 ** n) – это то же самое, что x & ((1 << n) - 1).

То есть x % 8 – это x & 7, а x % 256 – это x & 0xFF. В Python равенство выполняется для любых целых, включая отрицательные: -9 & 7 и -9 % 8 оба дают 7. Причина та же, что и с чётностью, – остаток по положительному модулю в Python неотрицателен, и младшие биты дополнительного кода дают ровно его.

Вместе с правилом из урока 6.2 получается полная пара: x >> n – частное от деления на 2 ** n, x & ((1 << n) - 1) – остаток.

`x − 1`: что происходит с битами

Ключ ко всем оставшимся идиомам – понять, как выглядит вычитание единицы на уровне битов. Смотрим на числе 12:

  00001100   (12)
- 00000001   (1)
= 00001011   (11)

Что произошло: младшая единица (она стояла в разряде 2) погасла, а все нули справа от неё зажглись. Это тот самый заём, который мы уже видели в уроке 6.3, когда разбирали формулу (1 << n) - 1: там из 00010000 получалось 00001111.

x - 1 гасит младшую единицу числа и зажигает все нули, стоявшие правее неё. Биты левее младшей единицы не меняются вообще.

Три примера подряд, чтобы правило стало очевидным:

12 → 11: 1100 → 1011, справа от единицы было два нуля – оба зажглись;
8 → 7: 1000 → 0111, тот же случай, только нулей три;
13 → 12: 1101 → 1100, справа от младшей единицы нулей не было – она просто погасла.

Из этого одного наблюдения дальше следует всё остальное.

`x & (x − 1)`: снять младшую единицу

Наложим x и x - 1 друг на друга по И и посмотрим на разряды по отдельности – как в уроке 6.1, столбик за столбиком.

Левее младшей единицы биты у обоих чисел одинаковые, и & оставляет их как есть. В самом разряде младшей единицы: у x единица, у x - 1 ноль – получается ноль. Правее: у x нули, у x - 1 единицы – снова нули.

  00001100   (12)
& 00001011   (11)
= 00001000   (8)

x & (x - 1) – это x с погашенной младшей единицей. Ровно один бит исчезает, все прочие остаются на местах.

Есть и зеркальная идиома, она встречается реже, но узнавать её стоит: x & -x оставляет только младшую единицу, гася всё остальное. 12 & -12 даёт 4. Работает она благодаря дополнительному коду из урока 5.2: -x – это ~x + 1, и после такой инверсии со сложением единственный разряд, где у x и -x совпали единицы, – как раз младший поднятый.

Две идиомы дополняют друг друга: одна младшую единицу забирает, другая – только её и оставляет.

В виджете ниже можно посмотреть первую из них на своих числах: поставьте в a любое значение, в b – на единицу меньше. Что стоит попробовать:

a = 12, b = 11 → 8: погасла единственная младшая единица;
a = 16, b = 15 → 0: у степени двойки единица одна, после неё не остаётся ничего;
a = 13, b = 12 → 12: справа от младшей единицы нулей не было;
a = 255, b = 254 → 254: погас младший бит, семь старших не тронуты.

Проверка на степень двойки

Первое следствие. У степени двойки в двоичной записи ровно одна единица: 1, 10, 100, 1000… Значит, если снять младшую единицу, не останется ничего.

x > 0 and x & (x - 1) == 0 – число x является степенью двойки.

Проверяем на двух числах:

16 = 10000, 16 & 15 = 10000 & 01111 = 0 → степень двойки;
12 = 1100, 12 & 11 = 1000 = 8, а это не 0 → не степень.

Теперь про первую половину условия, которую часто забывают. Для x = 0 выражение 0 & (0 - 1) даёт 0 – и без проверки x > 0 ноль объявился бы степенью двойки, хотя это не так. Для отрицательных ответ тоже окажется неверным. Это типичная ошибка: идиому запоминают в укороченном виде, а охраняющее условие теряется.

Зачем такая проверка нужна на практике: размеры буферов, ёмкости хеш-таблиц и стороны текстур в графике почти всегда делают степенями двойки – тогда деление и остаток заменяются сдвигом и маской, теми самыми из начала урока. И перед этим полезно убедиться, что размер действительно степень двойки, а не просто похож на неё.

Сколько единиц в числе

Второе следствие, и задача классическая: посчитать, сколько в числе единичных битов. В литературе эту величину называют весом Хэмминга, а процессорную инструкцию для неё – popcount.

Два способа, от прямолинейного к хитрому:

Цикл по разрядам – брать (x >> i) & 1 для каждого i, ровно как в уроке 6.2, и складывать полученные нули и единицы. Работает, но проходит все разряды, в том числе нулевые.
x = x & (x - 1) в цикле – каждый шаг гасит ровно одну единицу, поэтому итераций будет столько, сколько единиц в числе, и ни одной лишней. У числа 1 000 000 000 их 13 – тринадцать шагов вместо тридцати.

Есть и третий, самый честный: в Python 3.10 и новее у целых чисел есть готовая встроенная возможность – x.bit_count(). Если версия позволяет, в настоящем коде писать нужно именно её. Запись через точку мы подробно разберём в блоке 8, пока достаточно знать, что она существует и сразу даёт ответ. Приём с x & (x - 1) мы разбираем не потому, что он нужен ежедневно, а потому что он показывает, как из одного свойства битов вырастает целый алгоритм.

Про название: третий способ часто зовут алгоритмом Кернигана – по книге Кернигана и Ритчи о языке C, где он приведён как упражнение. Придуман он раньше: Питер Вегнер опубликовал его в журнале Communications of the ACM в мае 1960 года, а независимо от него тот же приём нашёл Деррик Лемер. Имя закрепилось за учебником, а не за автором – как и в случае с архитектурой фон Неймана из урока 1.2.

В виджете ниже алгоритм работает по шагам на числе 156, это 10011100. Следите за строкой x: на каждой итерации из неё уходит ровно одна единица, справа налево.

Обмен двух переменных через XOR

Вторая строка из начала урока. Здесь работает обратимость XOR из урока 6.1: x ^ x = 0 и (x ^ k) ^ k = x.

Классические три строки, меняющие местами значения a и b без третьей переменной:

a = a ^ b
b = b ^ a
a = a ^ b

Разберём по шагам для a = 12, b = 10:

Шаг	a	b	Что произошло
старт	12	10
`a = a ^ b`	6	10	в `a` лежит «смесь» обоих значений
`b = b ^ a`	6	12	`10 ^ 6` вернуло исходное значение `a`
`a = a ^ b`	10	12	`6 ^ 12` вернуло исходное значение `b`

Ключ к пониманию – вторая строка таблицы. После первого шага a – это не «испорченное» значение, а обе величины, сложенные обратимо. Из такой смеси XOR с любой из них достаёт вторую. Третья переменная не нужна: место для хранения нашлось внутри самих чисел.

Почему этот трюк не надо писать

А теперь честно – и это важнее самого приёма. Обмен через XOR любят показывать как красивый фокус, но в реальном коде ему место разве что в учебнике.

В Python обмен пишется как a, b = b, a. Одна строка, читается мгновенно, работает с любыми типами, а не только с целыми числами. Три строки с ^ не дают взамен ничего.
Он не быстрее. Когда-то приём экономил регистр процессора – на машинах, где свободных регистров было три-четыре. Современный компилятор меняет значения местами лучше, а в Python выигрыш и вовсе воображаемый: три операции вместо одной.
И у него есть настоящая ловушка. Если обменивать элемент сам с собой – arr[i] и arr[j] при совпавших i и j, – то первая же строка его обнулит: x ^ x = 0, и значение потеряно навсегда. В коде, который переставляет элементы списка, такой случай вполне реален, а ошибка получается тихая и трудноуловимая.

Вывод стоит запомнить именно в такой формулировке: этот приём нужно уметь прочитать в чужом коде и не нужно писать в своём.

Где XOR действительно выигрывает

Чтобы урок не оставил впечатления, будто XOR – это только про фокусы, разберём задачу, где он даёт по-настоящему лучшее решение.

Здесь нам понадобится список – по-настоящему мы займёмся им в блоке 9, а пока хватит одной фразы: список это несколько значений, записанных в квадратных скобках через запятую, например [4, 7, 1, 4, 7]. Уже знакомый нам for умеет проходить по такому списку так же, как проходил по range() в уроке 4.4: for v in [4, 7, 1, 4, 7]: – и на каждом витке v по очереди становится очередным числом списка. Больше про списки в этом уроке знать не нужно.

Условие. В списке все числа встречаются парами, и только одно – в единственном экземпляре. Найти его.

Очевидный путь – считать, сколько раз встретилось каждое число, и найти то, у которого счётчик равен единице. Работает, но требует памяти под все различные значения.

Решение через XOR: применить ^ ко всем элементам подряд, накапливая результат в одной переменной. Парные числа взаимно уничтожаются – x ^ x = 0, – а порядок значения не имеет: XOR коммутативен и ассоциативен, поэтому элементы можно мысленно переставить так, чтобы пары стояли рядом. В конце останется ровно непарный элемент.

Для списка [4, 7, 1, 4, 7] получится 1. Один проход, ноль дополнительной памяти, одна переменная-накопитель. Здесь трюк уже не косметический: он меняет требования к памяти с «зависит от данных» на «всегда одна переменная».

Все идиомы в интерпретаторе

x = 156
print(f'{x:08b}')             # 10011100

# Чётность и остаток по маске
print(x & 1, (x + 1) & 1)     # 0 1
print(x & 7, x % 8)           # 4 4   – маска младших трёх битов
print(-9 & 7, -9 % 8)         # 7 7   – в Python совпадает и для отрицательных

# Младшая единица: снять и выделить
print(bin(12), bin(11))       # 0b1100 0b1011
print(12 & 11)                # 8     – младшая единица погасла
print(12 & -12)               # 4     – осталась только она

# Степень двойки
n = 16
print(n > 0 and n & (n - 1) == 0)   # True
n = 12
print(n > 0 and n & (n - 1) == 0)   # False
n = 0
print(n > 0 and n & (n - 1) == 0)   # False – ради этого случая и нужно n > 0

# Сколько единиц в числе
print((156).bit_count())      # 4     – готовый ответ, Python 3.10 и новее

n = 156
count = 0
while n:
    n = n & (n - 1)           # гасим младшую единицу
    count = count + 1
print(count)                  # 4     – ровно четыре итерации

# Обмен через XOR и обмен по-питоновски
a, b = 12, 10
a = a ^ b
b = b ^ a
a = a ^ b
print(a, b)                   # 10 12

a, b = 12, 10
a, b = b, a                   # так и надо писать
print(a, b)                   # 10 12

# Непарный элемент: пары уничтожают друг друга
# [4, 7, 1, 4, 7] – список; for перебирает его элементы по одному
odd = 0
for v in [4, 7, 1, 4, 7]:
    odd = odd ^ v
print(odd)                    # 1

Шпаргалка по идиомам

Всё, что стоит держать перед глазами:

Выражение	Что делает	Почему работает
`x & 1`	чётность: 1 у нечётных, 0 у чётных	все веса разрядов, кроме нулевого, чётные
`x & ((1 << n) - 1)`	остаток от деления на `2 ** n`	маска младших n битов
`x >> n`	частное от деления на `2 ** n`	биты уезжают вправо
`x - 1`	гасит младшую единицу, зажигает нули справа от неё	заём при вычитании
`x & (x - 1)`	снимает младшую единицу	слева биты совпадают, справа обнуляются
`x & -x`	оставляет только младшую единицу	`-x` – это `~x + 1`
`x > 0 and x & (x - 1) == 0`	x – степень двойки	у степени двойки единица одна
`while x: x &= x - 1`	подсчёт единиц: шагов столько, сколько единиц	каждый шаг гасит ровно одну
`a ^= b; b ^= a; a ^= b`	обмен без третьей переменной	обратимость XOR

Важная оговорка ко всей таблице: она нужна прежде всего для чтения чужого кода. В своём, если вы не решаете задачу про биты специально, понятнее будут x % 2, x // 8, x.bit_count() и a, b = b, a. Короткая запись – не то же самое, что хорошая: n & 1 экономит три символа по сравнению с n % 2 == 1, а времени на чтение отнимает больше. Если идиома всё же нужна, поможет комментарий или имя: is_odd = n & 1 читается куда лучше, чем то же выражение посреди длинного условия.

Ответы к разминке

Все четыре фрагмента из начала урока теперь читаются без загадок:

if n & 1: – «если n нечётно»;
три строки с ^= – обмен значений a и b без третьей переменной;
x & (x - 1) == 0 – «у x не больше одной единицы», то есть проверка на степень двойки, если не забыть про x > 0;
цикл while x: x &= x - 1 – подсчёт единичных битов, по одному за итерацию.

Коротко

x & 1 – чётность: 1 у нечётных, 0 у чётных. Все веса разрядов, кроме нулевого, чётные, поэтому чётность решает один-единственный бит.
x & ((1 << n) - 1) – остаток от деления на 2 ** n, x >> n – частное. Вместе это полная замена деления с остатком на степень двойки, и в Python она верна даже для отрицательных чисел.
x - 1 гасит младшую единицу числа и зажигает все нули правее неё; биты левее не меняются. Из этого одного факта следует всё остальное.
x & (x - 1) снимает младшую единицу, x & -x – наоборот, оставляет только её.
x > 0 and x & (x - 1) == 0 – проверка на степень двойки. Без первой половины условия ноль ошибочно объявляется степенью двойки.
Единицы в числе считают либо перебором разрядов через (x >> i) & 1, либо циклом while x: x &= x - 1 – в нём ровно столько шагов, сколько единиц. В настоящем коде есть готовое x.bit_count() (Python 3.10 и новее).
Обратимость XOR даёт обмен двух переменных без третьей и поиск непарного элемента за один проход без дополнительной памяти. Обмен, впрочем, в Python пишут как a, b = b, a: вариант с ^ не быстрее и ломается, если обменивать элемент сам с собой.
Идиомы нужно уметь читать; писать их стоит только там, где вы действительно думаете о битах. Короткая запись – не то же самое, что хорошая.

И весь блок в четырёх словах. С битами числа мы научились делать четыре вещи: комбинировать их операциями &, |, ^, ~; двигать сдвигами << и >>; адресовать маской, где сама маска выбирает разряды, а операция задаёт действие; узнавать готовые выражения в чужом коде. Биты – это не «низкий уровень для избранных», а язык, на котором записаны форматы файлов, сетевые пакеты, права доступа и регистры устройств. Программируя на Python, вы вправе почти никогда не писать & и ^ руками. Но чтобы прочитать чужое решение, разобрать формат данных или понять, почему -7 >> 1 равно −4, этот язык нужно знать.