Операции сдвига << и >> – Учебник

6.2

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

Начнём не с битов, а с десятичной привычки. Чтобы умножить 25 на 100, никто не считает в столбик – просто приписывают справа два нуля. Почему это работает?

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

В двоичной системе основание равно двум, и у этого переезда есть собственные операторы – << и >>. Из них и из операций &, |, ^ собран весь инструментарий работы с битами: одни комбинируют разряды на месте, другие перемещают.

В этом уроке: сдвиг влево и почему он равен умножению на степень двойки; что происходит с битами, уехавшими за край, и чем Python отличается здесь от языков с фиксированной разрядностью; сдвиг вправо как деление нацело; арифметический сдвиг отрицательных чисел; приоритет сдвигов и ловушка 1 << 2 + 3; три идиомы – 1 << k, (x >> k) & 1, x | (1 << k) – и упаковка нескольких значений в одно число.

Разминка. Прежде чем читать дальше, предскажите результат каждой строки:

print(3 << 2)
print(40 >> 3)
print(-7 >> 1)

Первые две угадываются, если поверить в аналогию с приписыванием нуля. Третья – почти никогда: -7 >> 1 даёт −4, хотя «половина от −7» ожидалась бы как −3 или −3,5. К концу урока станет понятно и это.

Сдвиг влево (`<<`): приписываем нули справа

Сдвиг влево (оператор <<) перемещает все биты числа на заданное количество разрядов в сторону старших. Освободившиеся младшие разряды заполняются нулями.

Посчитаем 3 << 2 в восьми битах, в столбик:

   00000011   (3)
<< 2
=  00001100   (12)

Единицы стояли в разрядах 0 и 1 – переехали в разряды 2 и 3. Справа въехали два нуля, слева два разряда уехали за край, но там были нули, и терять было нечего.

Обратите внимание на устройство записи: в отличие от & и | из прошлого урока, здесь операнды разнородные. Слева – число, биты которого двигаем, справа – на сколько разрядов. Читается «три сдвинуть влево на два».

Почему сдвиг влево – это умножение

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

Когда бит переезжает на один разряд влево, его вес удваивается. Все биты переезжают одновременно – значит, удваивается и вся сумма. Отсюда формула:

x << k – это то же самое, что x * 2**k.

Проверяем: 3 << 2 – это 3 * 4, то есть 12; 5 << 1 = 10; 1 << 10 = 1024. И та же логика, что в разминке: в десятичной системе сдвиг на разряд умножает на 10, в двоичной – на 2, в восьмеричной – на 8. Правило одно, отличается только основание.

Отдельно стоит запомнить частный случай 1 << k – это число, у которого поднят ровно один бит, тот самый разряд k: 1 << 0 = 1, 1 << 3 = 8, 1 << 7 = 128. Самый короткий способ записать «вес разряда k» и главный кирпич следующего урока про маски.

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

Куда деваются биты, уехавшие за край

Здесь важно развести Python и языки с фиксированной разрядностью, иначе останется ложное впечатление.

В Python тип int не имеет фиксированной ширины (урок 5.1), поэтому при сдвиге влево ничего не теряется: число просто становится длиннее. 1 << 100 – совершенно законное значение из 31 десятичной цифры.

В C, C++ и Java всё иначе. Там число живёт в ячейке фиксированного размера, и биты, уехавшие за её границу, пропадают: результат оказывается обрезанным. Классический пример – 1 << 31 в 32-битном знаковом типе: единица заезжает в знаковый разряд, и вместо двух миллиардов получается отрицательное число. Это и называют переполнением.

Вернитесь к виджету выше и нажмите переключатель «Python: int без границ» – он станет «ячейка 8 бит». Возьмите x = 200 и сдвиг на 1: в режиме Python получится 400, а в восьмибитной ячейке – 144, потому что старший бит уехал за край и потерян. Одна и та же операция, разные ответы – разница только в том, есть ли у числа граница.

Если такое поведение нужно смоделировать в Python, результат ограничивают маской – тем же приёмом, что и в прошлом уроке: (200 << 1) & 0xFF даёт 144.

И две технические мелочи, чтобы не спотыкаться: сдвиг на отрицательное число – ошибка (ValueError: negative shift count), «сдвинуть влево на −2» вместо «вправо на 2» написать нельзя; а сдвиг влево на очень большое k честно построит огромное число и займёт память – Python не предупредит.

Сдвиг вправо (`>>`): деление с потерями

Сдвиг вправо (оператор >>) перемещает биты в сторону младших разрядов. Биты, уехавшие за правый край, теряются безвозвратно.

Столбик для 40 >> 3:

   00101000   (40)
>> 3
=  00000101   (5)

40 – это 5 * 8, и результат ровно 5: сдвиг вправо на k разрядов делит на 2**k. Но с оговоркой, которой не было у сдвига влево. Влево за край уезжали старшие разряды, и в нашем примере они были пустыми. Вправо уезжают младшие биты – а в них информация была.

Смотрите: 41 >> 1 даёт 20, а не 20.5. Уехавший младший бит был единицей – это остаток от деления, и он просто выпал.

x >> k – это целочисленное деление на 2**k, то есть x // 2**k, а не x / 2**k. Дробная часть не округляется, она отбрасывается вместе с уехавшими битами.

Сдвиг вправо у отрицательных чисел

Пора вернуться к третьей строке разминки. И снова всё решает дополнительный код из урока 5.2.

У отрицательного числа в дополнительном коде слева – бесконечная цепочка единиц (мы это уже видели в уроке 6.1, когда разбирались с ~). При сдвиге вправо биты едут вниз, и слева что-то должно въезжать. Если въедут нули, знак потеряется: −7 внезапно станет большим положительным числом. Поэтому используется арифметический сдвиг – слева въезжает копия знакового бита. У отрицательного числа это единицы, у положительного нули, и знак сохраняется сам собой.

Проверим -7 >> 1:

   …1111001   (−7)
>> 1
=  …1111100   (−4)

Число осталось отрицательным, и получилось −4. Тот же ответ даёт -7 // 2, потому что // округляет вниз, в сторону минус бесконечности, а не «к нулю»: −3.5, округлённое вниз, – это −4.

Соберём ответ на вопрос «почему −4, а не −3» в одну фразу, её стоит запомнить дословно: слева въезжает копия знакового бита, поэтому число остаётся отрицательным, а уехавший младший бит просто теряется – получается деление нацело с округлением вниз, ровно как у //.

Значит, правило x >> k = x // 2**k работает и для отрицательных чисел без исключений – именно потому, что и сдвиг, и // округляют в одну и ту же сторону. А вот int(-7 / 2) даст −3: обычное деление с отбрасыванием дробной части – это уже другая операция.

Отсюда же ещё одно следствие: сдвигая отрицательное число вправо сколько угодно долго, вы получите не 0, а −1 (-7 >> 10 → −1). Бесконечная цепочка единиц никуда не девается.

Всё это можно посмотреть по шагам в виджете выше: переключите операцию на «>> вправо», включите «знаковое» и введите −7. Жёлтые разряды слева – то, что въехало, пунктирные ячейки справа – выпавшие биты, то есть остаток от деления.

Приоритет: главная ловушка сдвигов

В таблице приоритетов из прошлого урока сдвиги стоят между арифметикой и побитовыми операциями: << и >> слабее + и −, но сильнее &, ^, |.

Из этого следует ошибка, которую глазами не поймать:

1 << 2 + 3 – это 1 << 5, то есть 32, а вовсе не (1 << 2) + 3 = 7. Программа не падает, просто считает не то;
x >> 4 & 1 – а здесь порядок как раз ожидаемый: (x >> 4) & 1, потому что сдвиг сильнее &.

Практический вывод тот же, что и в уроке 6.1: там, где сдвиг соседствует с арифметикой, скобки ставим всегда. (1 << 2) + 3 читается однозначно и не требует держать таблицу приоритетов в голове.

Сдвиги в интерпретаторе

print(3 << 2)              # 12  – 3 · 4, биты уехали на два разряда влево
print(1 << 10)             # 1024 – единица в десятом разряде
print(bin(3), bin(3 << 2)) # 0b11 0b1100 – те же две единицы, другие разряды

print(40 >> 3)             # 5   – это 40 // 8
print(41 >> 1)             # 20  – младший бит потерян вместе с остатком
print(-7 >> 1, -7 // 2)    # -4 -4 – знак сохранён, округление вниз
print(-7 >> 10)            # -1  – цепочка единиц слева не кончается

# В Python сдвиг влево ничего не теряет: у int нет фиксированной ширины
print(1 << 100)            # 1267650600228229401496703205376
print(200 << 1)            # 400
print((200 << 1) & 0xFF)   # 144 – а так ведёт себя восьмибитная ячейка

# Ловушка приоритета: сдвиг слабее сложения
print(1 << 2 + 3)          # 32, а не 7
print((1 << 2) + 3)        # 7

Сдвиг вместе с `&`: достать конкретный бит

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

Достать бит номер k – подвинуть его в самый младший разряд и отфильтровать всё остальное: (x >> k) & 1. На числе 13, это 1101: (13 >> 1) & 1 даёт 0, а (13 >> 2) & 1 – 1.

Тем же способом строится и обратная операция – поднять нужный бит, – но там уже целая система приёмов, и ей посвящён весь урок 6.3.

В виджете ниже (x >> k) & 1 работает внутри цикла, который собирает двоичную запись числа: на каждом шаге программа берёт младший бит через & 1, приписывает его слева к строке и сдвигает число вправо. По сути это ручная реализация bin() из урока 2.6 – и одновременно тот же алгоритм деления уголком из 2.5, только деление на 2 заменено сдвигом.

Где сдвиги встречаются на практике

Три сюжета, коротко.

Упаковка нескольких значений в одно число. Цвет в формате RGB – это три числа от 0 до 255, а хранится он одним: (r << 16) | (g << 8) | b. Именно так записан цвет #FF8800 в CSS и в графических форматах. Обратная операция – распаковка сдвигом и маской, о ней подробно в уроке 6.3.
Степени двойки. 1 << k – самый лаконичный способ записать 2**k, когда речь про размеры буферов, ёмкость памяти и границы диапазонов. Диапазон n-битного знакового числа из урока 5.2 записывается так: от -(1 << (n - 1)) до (1 << (n - 1)) - 1.
Хеш-функции и генераторы случайных чисел. Сдвиги вперемешку с XOR «размешивают» биты – на этом построены и хеш-таблицы, и простые генераторы псевдослучайных чисел.

И честная оговорка, в тон прошлому уроку: писать x << 1 вместо x * 2 ради скорости сегодня не нужно. Когда-то это был реальный приём оптимизации – сдвиг выполнялся заметно быстрее умножения. Сейчас компиляторы сами заменяют умножение на константу сдвигом, а в Python любой такой выигрыш теряется на фоне остальных расходов. Сдвиг стоит писать там, где вы действительно думаете о битах: тогда он и читается правильно. В арифметической формуле x * 2 понятнее, чем x << 1.

Упаковка и распаковка цвета

r, g, b = 255, 136, 0        # оранжевый

color = (r << 16) | (g << 8) | b
print(color)                 # 16746496
print(hex(color))            # 0xff8800 – знакомая запись цвета

# Распаковка: подвинуть нужное поле вниз и отрезать лишнее
print((color >> 16) & 0xFF)  # 255 – красный
print((color >> 8) & 0xFF)   # 136 – зелёный
print(color & 0xFF)          # 0   – синий

Обе операции разом

Три числа заняли один int, и переход между «удобно человеку» и «удобно хранить» уложился в пару строк со сдвигами. Шестнадцатеричная запись здесь не случайна: как мы разбирали в уроке 2.3, одна hex-цифра – ровно 4 бита, поэтому байт всегда занимает ровно две цифры и поля видны глазами.

Сводная таблица по уроку:

Оператор	Что делает с битами	Чем является арифметически	Что теряется
`x << k`	двигает к старшим разрядам, справа въезжают нули	умножение на `2**k`	в Python ничего; при фиксированной ширине – старшие биты
`x >> k`	двигает к младшим разрядам, слева въезжает знаковый бит	деление нацело на `2**k` (`//`, округление вниз)	младшие биты, то есть остаток

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

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

3 << 2 → 12: биты переехали на два разряда влево, вес каждого вырос вчетверо;
40 >> 3 → 5: деление на 8 нацело, а уехавшие младшие биты были нулевыми – терять было нечего;
-7 >> 1 → −4: слева въехали копии знакового бита, знак сохранился, а округление пошло вниз – ровно как у //.

Коротко

Сдвиг перемещает биты по разрядам, меняя их вес: x << k = x * 2**k, x >> k = x // 2**k.
Влево справа въезжают нули. В Python при этом ничего не теряется – у int нет фиксированной ширины; в языках с ячейкой фиксированного размера старшие биты уходят за край, и это называется переполнением. В Python такое поведение моделируют маской: (200 << 1) & 0xFF = 144.
Вправо биты теряются безвозвратно, поэтому >> – деление нацело, а выпавшие биты и есть остаток: 41 >> 1 = 20.
Сдвиг вправо арифметический: слева въезжает копия знакового бита, поэтому отрицательное число остаётся отрицательным, а округление идёт вниз – так же, как у //. Отсюда -7 >> 1 = −4, а -7 >> 10 = −1, но не 0.
Сдвиг на отрицательное число – ошибка ValueError; «сдвинуть влево на −2» вместо «вправо на 2» написать нельзя.
Приоритет: сдвиги слабее + и −, но сильнее &, ^, |. Поэтому 1 << 2 + 3 даёт 32, а не 7 – рядом с арифметикой ставьте скобки.
Две идиомы, которые стоит запомнить целиком: 1 << k – вес разряда k, число с единственной единицей; (x >> k) & 1 – значение бита k. Из них в уроке 6.3 вырастут битовые маски.
Сдвиг вместе с | упаковывает несколько значений в одно число ((r << 16) | (g << 8) | b), а сдвиг вместе с маской распаковывает обратно.
Писать x << 1 вместо x * 2 ради скорости не нужно: выигрыша нет, а читаемость страдает. Сдвиг уместен там, где речь действительно о битах.