Битовые сдвиги: shl, shr, sar

Урок про сдвиги — быстрый способ умножать и делить на степени двойки и упаковывать биты.

Сдвиг двигает все биты числа влево или вправо на заданное число позиций, дополняя освободившиеся места.

Сдвиг влево умножает

Команда shl rax, 1 сдвигает биты на одну позицию влево, добавляя ноль справа. Это эквивалентно умножению на 2. Сдвиг на n позиций — умножение на 2 в степени n:

  0000 0011  (3)
  shl 1 ->  0000 0110  (6)
  shl 1 ->  0000 1100  (12)

Поэтому shl rax, 3 — это умножение на 8, и оно гораздо быстрее команды mul. Компиляторы постоянно так оптимизируют умножение на константы-степени двойки.

Два вида сдвига вправо

Сдвиг вправо делит на 2, но с числами со знаком возникает вопрос, чем заполнять старший бит:

Для отрицательного числа shr «потеряет» знак и сделает его огромным положительным, а sar сохранит знак — поэтому деление знакового на 2 это sar, а не shr.

Как работает под капотом

Проверим связь сдвига и умножения/деления на Python:

x = 3
print("3 << 1 =", x << 1)   # умножить на 2
print("3 << 3 =", x << 3)   # умножить на 8

y = 40
print("40 >> 1 =", y >> 1)  # делить на 2
print("40 >> 2 =", y >> 2)  # делить на 4

Вывод:

3 << 1 = 6
3 << 3 = 24
40 >> 1 = 20
40 >> 2 = 10

Сдвиг — одна из самых дешёвых операций процессора (часто 1 такт), поэтому замена умножения/деления на степени двойки сдвигом — классический приём оптимизации. Деление сдвигом возможно только на степени двойки; для остальных делителей нужен div.

Частые ошибки

• Делить знаковое число через shr. Отрицательное превратится в большое положительное; нужен sar.
• Думать, что сдвигом можно делить на любое число. Только на степени двойки (2, 4, 8, 16…).
• Игнорировать выпавшие биты. При сдвиге влево старшие биты теряются — может случиться переполнение.

Итог

• Сдвиг влево shl — умножение на степень двойки.
• Сдвиг вправо делит на степень двойки: shr для беззнаковых, sar для знаковых.
• Сдвиги дешевле mul/div, поэтому компиляторы их активно применяют.
• Делить сдвигом можно только на 2, 4, 8 и другие степени двойки.