Шесть операций над битами: И, ИЛИ, исключающее ИЛИ, НЕ и два сдвига

Если ты без запинки скажешь, чему равны 12 & 10, 12 ^ 10 и 1 << n + 1, и достанешь третий байт из 32-битного числа сдвигом и маской, - листай до «Теперь сам».

Как думаешь, чему равно 1 << n + 1

Нужно число, у которого стоят два бита: бит номер n и самый младший. При n = 3 это 1001₂ = 9. Написана строка 1 << n + 1: сдвиг 1 << n ставит единицу в бит номер n, а + 1 должен добавить младший бит.

Прежде чем читать дальше, реши: 9 или что-то другое? Ответ - 16. Сдвиг в Python слабее сложения, и строка читается как 1 << (n + 1). Нужно было (1 << n) + 1. Скобки в битовых выражениях - не украшение, и ниже будет строка с порядком действий, по которой видно, где они обязательны.

На что это похоже

Представь два ряда выключателей одинаковой длины, один под другим. Над каждой парой выключателей висит лампочка. Правило &: лампочка горит, если включены оба. Правило |: если включён хотя бы один. Правило ^: если включён ровно один.

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

Механизм: разряды, три попарных действия, переворот и сдвиги

Бит - один двоичный разряд, ноль или единица. Число записано битами так же, как цифрами, только вес разряда - степень двойки, а не десятки: 1100₂ = 8 + 4 = 12, 1010₂ = 8 + 2 = 10. Биты нумеруют справа, с нуля: бит номер k весит 2ᵏ. В Python двоичную запись пишут с приставкой 0b, шестнадцатеричную - с 0x; одна шестнадцатеричная цифра - ровно четыре бита, поэтому 0xFF - это восемь единиц.

        1100   = 12            1100   = 12            1100   = 12
     &  1010   = 10         |  1010   = 10         ^  1010   = 10
        ----                   ----                   ----
        1000   = 8             1110   = 14            0110   = 6
     единица у обоих        хотя бы у одного        биты разные

~x переворачивает каждый бит. x << k дописывает справа k нулей, то есть умножает на 2ᵏ: сдвиг на разряд влево в двоичной записи - то же, что приписать ноль в десятичной. x >> k отбрасывает k младших битов - делит на 2ᵏ с округлением вниз.

def bity(x, n):
    return bin(x)[2:].zfill(n)

a = 0b1100
b = 0b1010
print(bity(a & b, 4), a & b)
print(bity(a | b, 4), a | b)
print(bity(a ^ b, 4), a ^ b)
print(a << 2, a >> 2, ~a)

1000 8
1110 14
0110 6
48 3 -13

bin(x) даёт строку вида 0b1100; срез [2:] убирает приставку, zfill(n) дополняет нулями слева до n знаков. Последнее число в выводе выглядит странно: ~12 равно -13, а не 0011₂ = 3. У целого в Python нет ширины, слева от записи стоит бесконечный ряд нулей, и переворот превращает его в бесконечный ряд единиц - так записано отрицательное число. Откуда именно -13, разбирает следующий урок; пока достаточно формулы ~x = -x - 1.

Порядок действий. От слабого к сильному:

сравнения  <  |  <  ^  <  &  <  сдвиги  <  + и -  <  * / // %  <  ~ и унарный минус  <  **

Знак < в этой строке читается «слабее»; унарный минус - минус перед одним числом, как в -x. Сложение сильнее сдвига - отсюда 1 << n + 1. Сравнение слабее всех побитовых - поэтому x & 1 == 0 в Python значит (x & 1) == 0, как и хочется.

Правило

x >> k & 1 - бит номер k. x & m оставляет от x только биты, отмеченные в m; такое m называют маской. x << k | y приставляет y справа к x, если y занимает не больше k битов. (1 << k) - 1 - маска из k младших единиц. Сдвиг слабее сложения и вычитания, поэтому скобки вокруг 1 << k в последней записи обязательны.

Маска - число, которое используют не как количество, а как трафарет: единицы в нём показывают, какие разряды другого числа нужны.

Разбор: достать бит и вырезать кусок

Число 43 - это 101011₂. Нужен бит номер 3.

x      = 101011
x >> 3 = 101          три младших бита ушли, нужный бит стал самым правым
& 1    =   1          от всего числа остался один разряд

43 >> 3 & 1 равно 1, 43 >> 2 & 1 равно 0. Скобки не нужны: сдвиг сильнее &.

Тем же способом вырезается кусок из нескольких битов. Цвет точки на экране хранится одним числом из шести шестнадцатеричных цифр - по две, то есть по восемь битов, на красный, зелёный и синий. Для 0x2E8B57:

красный   0x2E8B57 >> 16 & 0xFF  =  0x2E  =  46
зелёный   0x2E8B57 >> 8  & 0xFF  =  0x8B  =  139
синий     0x2E8B57       & 0xFF  =  0x57  =  87

Сдвиг подводит нужный кусок к правому краю, маска 0xFF срезает всё, что левее. Обратная сборка - 46 << 16 | 139 << 8 | 87. Здесь | работает как сложение, потому что куски не пересекаются: там, где у одного слагаемого стоят биты, у остальных нули.

Разбор: адрес сети, и где маска слишком длинна для тренажёра

IPv4-адрес - 32 бита, четыре байта подряд; в привычной записи каждый байт дан десятичным числом, старший слева. Запись 192.168.1.130/26 говорит, что старшие 26 битов - номер сети, а оставшиеся шесть - номер узла в ней. «Маска подсети» - маска в том самом смысле: 26 единиц и шесть нулей.

def v_chislo(a, b, c, d):
    return a << 24 | b << 16 | c << 8 | d

def v_adres(x):
    return [x >> 24 & 255, x >> 16 & 255, x >> 8 & 255, x & 255]

m26 = 0xFFFFFFFF << 6 & 0xFFFFFFFF
adres = v_chislo(192, 168, 1, 130)
print(v_adres(m26), v_adres(adres & m26), adres & ~m26)

[255, 255, 255, 192] [192, 168, 1, 128] 2

Маска строится сдвигом: 32 единицы уезжают влево на шесть разрядов, справа появляются шесть нулей, а второе & 0xFFFFFFFF срезает то, что вылезло за 32-й бит. Адрес сети - адрес & маска, номер узла - адрес & ~маска: у .130 это сеть .128 и узел 2. ~m26 - отрицательное число, но & с положительным адресом сам срезает бесконечный ряд единиц слева. Два адреса лежат в одной сети, когда a & m == b & m: для .30 и .70 при /26 это неверно - сети 192.168.1.0 и 192.168.1.64.

Граница приёма - ширина числа. В C у переменной 32 или 64 бита, и 1 << 40 в 32-битном типе даёт неопределённый результат. В Python число растёт само, зато & с маской нужен там, где в C лишнее отрезалось бы без спроса - как в строке с m26. В тренажёре целое точно до 2⁵³ - почему именно столько, объяснит урок про биты дробного числа в конце раздела: маска из 52 битов работает, 1 << 53 останавливает программу с объяснением. Во всех уроках раздела примеры уложены в 32 бита, а 64-битные константы названы в тексте.

Что ломается без этого

Первое: скобки. 1 << n + 1, x & 0xFF + 1, 1 << k - 1 - во всех трёх сложение выполнится раньше. В C хуже: там сравнение сильнее &, и x & 1 == 0 читается как x & (1 == 0), то есть всегда ноль. Код, перенесённый из Python в C без скобок, компилируется и врёт.

Второе: ^ вместо степени. 2 ^ 10 - не 1024, а 8: 0010 ^ 1010 = 1000. Степень - 2 ** 10 или 1 << 10.

Третье: | вместо + и наоборот. Пока куски не пересекаются, разницы нет. Как только пересеклись, + даёт перенос в чужой разряд: 0b0110 + 0b0100 = 0b1010, а 0b0110 | 0b0100 = 0b0110.

Четвёртое: ~ без маски. ~0x0F в Python равно -16, а не 0xF0. Нужны восемь битов - пиши ~0x0F & 0xFF.

Зачем это в работе

Права на файл в Unix - девять битов, и chmod 754 - это три маски по три бита: 7, 5 и 4 - это 111, 101 и 100, биты «чтение», «запись» и «запуск». Флаги системных вызовов склеиваются через |: O_WRONLY | O_CREAT | O_TRUNC. Адрес сети и широковещательный адрес считаются маской, и строка allow 192.168.1.0/26 в конфиге веб-сервера - сравнение адрес & маска с номером сети.

Сетевые протоколы и форматы файлов упаковывают поля плотнее байта: в заголовке IPv4 версия и длина заголовка делят один байт пополам, в заголовке TCP флаги SYN, ACK, FIN и остальные занимают соседние биты одного байта. Разобрать такой заголовок - значит сдвинуть и наложить маску.

И всё остальное в разделе - счёт единиц, множества в одном числе, арифметика без ветвлений - собрано из этих шести действий.

Теперь сам

1. Чему равны 12 & 10, 12 | 10, 12 ^ 10?
2. Запиши выражение для бита номер 5 числа x и вычисли его для x = 100.
3. Чему равно x & 0xF для x = 0x3A7, и что это за часть числа?
4. Что напечатает print(1 << 2 + 1, (1 << 2) + 1)?
5. Дата упакована как год << 9 | месяц << 5 | день. Достань месяц из числа 1037689.