Побитовый сдвиг - Как работает эта операция

Побитовый сдвиг — это операция, которая сдвигает двоичную запись целого числа на несколько позиций: << сдвигает влево, а >> — вправо. Обозначающие её операторы встречаются почти во всех популярных языках.

Математика: почему сдвиг — это умножение

Сдвиг — это операция над записью числа в позиционной системе счисления. Начнём с привычной десятичной: если приписать к числу ноль справа, оно вырастет в 10 раз — было 5, стало 50, было 123, стало 1230. Здесь то же правило: все разряды сдвигаются на позицию влево, а значит, число умножается на основание системы счисления.

В двоичной системе основание равно 2, поэтому каждый сдвиг влево удваивает число (в середине — результат в двоичной системе, справа — тот же результат в десятичной):

1 << 1  = 10        = 2
1 << 2  = 100       = 4
1 << 3  = 1000      = 8
1 << 8  = 100000000 = 256

Отсюда общее правило: a << N равносильно умножению a на 2 в степени N. Сдвигать можно любое число, не только единицу. Сдвинем влево число 5 (в двоичной записи — 101):

было:   | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |    = 5
         <-- <-- <-- <-- <-- <-- <-- <--   влево
стало:  | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |    = 10 = 5 * 2

Все разряды уехали на позицию влево, справа вошёл ноль — и число удвоилось.

А запись 1 << 100 — это самый короткий способ записать 2 в степени 100: единица и сто нулей в двоичной системе. В десятичной получается 31-значное число:

1 << 100 = 2^100 = 1267650600228229401496703205376

Зеркальная операция — сдвиг вправо >> — делит число на 2 в степени N, отбрасывая остаток:

было:   | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |    = 7
         --> --> --> --> --> --> --> -->   вправо
стало:  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |    = 3 = 7 / 2

Крайняя правая единица вылетела за край сетки — это и есть отбрасывание остатка.

На практике сдвиги используют, чтобы кратко записывать степени двойки (например, 1 << 10 = 1024 — как раз размер килобайта) и для работы с битовыми масками.

Сдвиги и разрядность: почему языки ведут себя по-разному

В математике количество цифр у числа не ограничено. В программе же целые числа обычно занимают фиксированные 64 бита, а для хранения 2^100 нужна 101 двоичная позиция.

Что происходит с «не поместившимися» битами, легко увидеть на маленькой разрядной сетке — возьмём всего 4 бита:

было:    | 0 | 0 | 0 | 1 |    = 1
1 << 3:  | 1 | 0 | 0 | 0 |    = 8 (впритык)
1 << 4:  | 0 | 0 | 0 | 0 |    = 0 (единица вылетела
                                 за левый край)

Всё то же самое происходит и в 64-битных числах, просто разрядов больше. Поэтому результат 1 << 100 зависит от языка:

// Go (нетипизированная константа): ровно 2^100
// Python:                           ровно 2^100
// JavaScript:                       16
// PHP:                              0

Go вычисляет константы на этапе компиляции с произвольной точностью, поэтому const c = 1 << 100 там законно — этот приём используется в уроке про константы курса Go. Python идёт дальше: у него даже обычные целые переменные не ограничены по разрядности.

В JavaScript побитовые операторы стандартизированы для 32-битных чисел, а величина сдвига берётся по модулю 32: 100 mod 32 = 4, поэтому фактически вычисляется 1 << 4 = 16. В PHP биты при таком сдвиге просто вылетают за пределы 64-битного числа, и остаётся 0. А в C и C++ сдвигать число шире, чем его собственный тип, вообще запрещено — это неопределённое поведение.

В JavaScript побитовые операторы стандартизированы для 32-битных чисел, а величина сдвига берётся по модулю 32 — то есть берётся остаток от деления количества позиций на 32: 100 mod 32 = 4.
Поэтому фактически вычисляется 1 . В PHP биты при таком сдвиге просто вылетают за пределы 64-битного числа, и остаётся 0. А в C и C++ сдвигать число шире, чем его собственный тип, вообще запрещено — это неопределённое поведение.

Запись в разных языках

Символы << и >> пришли из C, и точно так же сдвиг записывается почти во всех Си-подобных языках: C, C++, Java, C#, JavaScript, PHP, Python, Go, Rust и других. А вот, например, в Pascal и Delphi для этого служат ключевые слова shl и shr (от shift left / shift right).

Забавная деталь: в C++ символ << перегружен ещё и для вывода в поток — запись cout << "Привет" не имеет отношения к сдвигам, это то же обозначение, применённое к совершенно другому действию.