Операции сдвига

Операции сдвига – базовые битовые трансформации над двоичными представлениями целых чисел. Сдвиг позволяет за O(1) реализовывать умножение/деление на степени двойки, выделение и упаковку битовых полей, циклические повороты (ротации), эффективные маски и адресные расчёты. Для ЕГЭ по информатике уверенное владение сдвигами критично при анализе двоичных строк, вычислении значений по схеме «<< k»/«>> k», чтении программных фрагментов и доказательстве корректности манипуляций с битами.

Двоичная модель и знаковое представление

Пусть задано слово фиксированной ширины w бит, позиции нумеруются 0..w-1 (младший → старший бит).

• Двоичное представление числа x – вектор битов x_{w-1} … x_1 x_0.
• Для беззнаковых целых диапазон: 0 … 2^w - 1.
• Для знаковых целых в дополнительном коде:
• min_signed = -2^(w-1)
• max_signed =  2^(w-1) - 1

Старший бит x_{w-1} – знак (0 – неотриц., 1 – отриц.). Отрицательное x хранится как 2^w - |x|.

Маска полного слова:

FULL(w) = (1 << w) - 1

(для ограничений в формуле ротаций и усечения результата до w бит).

Виды сдвигов и их семантика

1. Логический левый сдвиг (LLS)
   

   y = x << k

   Биты смещаются в сторону старших разрядов, младшие k позиций заполняются нулями. Отбрасываются k старших битов, «вышедших» за границы w. Для беззнакового x и при отсутствии отброшенных единиц:

   y = (x * 2^k) mod 2^w

2. Логический правый сдвиг (LRS)
   

   y = x >> k    // логический

   Биты смещаются к младшим разрядам, старшие k позиций заполняются нулями:

   y = floor(x / 2^k)    // для беззнакового x

3. Арифметический правый сдвиг (ARS)
   

   y = x >>> k   // псевдосинтаксис; в ряде языков оформляется как signed >> k

   Сохраняет знак: старшие k позиций заполняются копией старшего бита исходника (x_{w-1}), то есть «распространяет» знак. В двухкомплементарной арифметике часто интерпретируется как деление на 2^k с округлением к минус бесконечности. Важно: в некоторых языках (C/C++) поведение >> для знаковых отрицательных – зависит от реализации; на практике почти всегда ARS, но переносимость требует осторожности.

4. Циклические сдвиги (ротации, ROL/ROR)
   

   Переносимые биты «вываливаются» с одного края и возвращаются на другой. Для ширины w:

   ROL_w(x, k) = ((x << k) | (x >> (w - k))) &; FULL(w)

   ROR_w(x, k) = ((x >> k) | (x << (w - k))) &; FULL(w)

   Здесь k обычно берут по модулю w: k := k mod w.

Алгебра и копируемые формулы

1. Умножение/деление на 2^k
   

   (беззнаковые)    x << k  = (x * 2^k) mod 2^w

   (беззнаковые)    x >> k  = floor(x / 2^k)

   (знаковые, ARS)  x >>> k ≈ floor_div(x, 2^k)   // округление вниз

   Важно: левый сдвиг эквивалентен умножению только если отброшенные старшие биты равны 0 (нет переполнения в фиксированной разрядности).

2. Извлечение и модификация битов
   

   Бит i:                bit(i)      = (x >> i) &; 1

   Установить бит i:     set(i)      = x | (1 << i)

   Сбросить бит i:       clear(i)    = x &; ~(1 << i)

   Инвертировать бит i:  toggle(i)   = x ^ (1 << i)

   Извлечь поле [l..r]:  field       = (x >> l) &; ((1 << (r-l+1)) - 1)

   Вставить поле v:      x'          = (x &; ~(((1 << L) - 1) << l)) | ((v &; ((1 << L) - 1)) << l)

   где L = r - l + 1

3. Сдвиги для двоичных строк (ЕГЭ)
   

   Если двоичная строка b = b_{m-1} … b_0 интерпретируется как беззнаковое число:

   b << k  ⇒ приписать справа k нулей

   b >> k  ⇒ отбросить k младших символов (слева дополнить нулями при отображении фиксированной ширины)

4. Нормализация ширины
   

   Любая операция над словом фиксированной ширины следует завершать усечением:

   normalize_w(y) = y &; FULL(w)

   Это гарантирует корректное «обрубание» лишних разрядов для чистых формул.

Правила корректности и переносимости

Правило 1 (диапазон сдвига). Сдвигать на k, где 0 ≤ k < w. Значение k ≥ w или отрицательное – ошибка/неопределённость (в C/C++ – UB; в Java/JavaScript – k берут по модулю 32/64).

Правило 2 (знаковость). Для правого сдвига различать: логический (заполнение нулями) и арифметический (пропагирование знака). В задачах ЕГЭ по умолчанию говорить о логическом правом сдвиге на двоичных строках.

Правило 3 (переполнение при LLS). Левый сдвиг «теряет» выходящие биты. Если моделируете умножение – заранее убедитесь, что старшие k битов нулевые:

(x >> (w - k)) = 0  ⇒  x << k = x * 2^k   (в пределах w)

Правило 4 (маски и поля). Любая операция вставки/извлечения поля должна использовать маски, явно фиксирующие длину поля и позицию (см. §3.2), и завершаться нормализацией ширины.

Правило 5 (ротации). Для переносимости формул ROL/ROR всегда дополняйте &; FULL(w) и берите k mod w.

Правило 6 (арифметический сдвиг знаковых). Если требуется «деление на 2^k» для отрицательных – используйте определённую семантику языка (например, в Python // округляет вниз, а >> для отрицательных – арифметический; в C/C++ – поведение зависит от реализации для отрицательных).

Практические паттерны (часто встречаются на ЕГЭ)

1. Быстрое умножение/деление на степени двойки
   

   a * 8  ⇔  a << 3

   a / 8  ⇔  a >> 3   // беззнаковое, либо явная оговорка про округление

2. Проверка чётности и кратности 2^k
   

   чётность:      (x &; 1) = 0

   кратность 2^k: (x &; ((1 << k) - 1)) = 0

3. Сдвиг и маска для выборки байта/полуслова
   

   Например, из 32-битного слова взять байт №2 (нумерация от младшего 0,1,2,3):

   byte2 = (x >> (8 * 2)) &; 0xFF

4. Поворот битовой «маски окна»
   

   Для скользящих шаблонов:

   win' = ((win << 1) | new_bit) &; FULL(w)

5. Упаковка/распаковка полей
   

   Допустим, A – 5 бит, B – 3 бита, C – 8 бит; формат [C|B|A] = 8+3+5 = 16:

   pack   = ((C &; ((1<<8)-1)) << (3+5)) | ((B & 7) << 5) | (A &; 31)

   unA    =  pack        &; 31

   unB    = (pack >> 5)  &; 7

   unC    = (pack >> 8)  &; 255

Асимптотика и аппаратные замечания

• Сдвиги выполняются за константное время на стандартной архитектуре (баррельный шифтер).
• Ротации часто поддерживаются отдельными инструкциями (ROL/ROR).
• В расчётах адресов, хешей и криптопримитивах (SHA, MD, ARX-конструкции) ротации критичны: используйте точные формулы с модулем по w.

Мини-шпаргалка (коротко и копируемо)

FULL(w)             = (1 << w) - 1

ROL_w(x,k)          = ((x << k) | (x >> (w - k))) &; FULL(w)

ROR_w(x,k)          = ((x >> k) | (x << (w - k))) &; FULL(w)

извлечь бит i       = (x >> i) &; 1

извлечь поле [l..r] = (x >> l) &; ((1 << (r-l+1)) - 1)

деление беззнаковое = x >> k = floor(x / 2^k)

умножение            = (x << k) при (x >> (w-k)) = 0

кратность 2^k        = (x &; ((1<<k)-1)) = 0

Пять упражнений 

Упражнение 1. Семантика и корректность LLS/LRS
Дан w=8, беззнаковые значения.
a) Вычислите в двоичном виде и в десятичном:
x = 0b00110101
x << 3 = ?
x >> 2 = ?
b) Докажите, что x << 3 = (x * 8) mod 256. Укажите, при каких x равенство сводится к обычному x * 8 без модуля.
c) Для каких k значение x << k гарантированно не переполнится (формула через старшие биты)?

Упражнение 2. Извлечение и вставка полей

Пусть w=16, слово строится как [C(8)|B(3)|A(5)] (см. §5.5).
a) Запишите функции pack(A,B,C) и обратные unA/​unB/​unC в виде формул.
b) Докажите, что unA(pack(A,B,C)) = A при условии 0 ≤ A < 2^5, 0 ≤ B < 2^3, 0 ≤ C < 2^8.
c) Как изменятся формулы, если порядок полей – [B|A|C]?

Упражнение 3. Ротации и нормализация ширины

Пусть w=8, x=0b10110001, k=3.
a) Вычислите ROL_8(x,3) и ROR_8(x,3) пошагово (с показом промежуточных «сдвигов» и OR).
b) Объясните, зачем нужен &; FULL(w) в формулах ротаций. Приведите контрпример без усечения.
c) Докажите, что ROL_w(ROR_w(x,k),k) = x при нормализации k := k mod w.

Упражнение 4. Правый сдвиг знаковых и деление

Рассматриваем w=8, дополнительный код. Пусть x = -5.
a) Запишите двоичное представление x и x >>> 1 (арифметический правый сдвиг).
b) Сравните x >>> 1 с x / 2 при двух вариантах округления: к нулю и вниз.
c) Объясните, почему переносимость требований к правому сдвигу знаковых значений – чувствительный момент; предложите безопасный способ реализовать «деление на 2^k с округлением вниз» независимо от реализации.

Упражнение 5. Быстрые проверки на ЕГЭ

Дано беззнаковое x ширины w.
a) Сформулируйте критерий кратности x числу 2^k через маску младших битов; докажите его.
b) Покажите, как извлечь байт №b (0 ≤ b ≤ w/8 - 1) из x.
c) Пусть дан фрагмент:
y = ((x << 5) | (x >> (w-5))) &; FULL(w)
Объясните смысл операции и её отличие от простого x << 5.

Заключение

Операции сдвига – математически строгий и аппаратно эффективный инструмент битовой обработки. Чёткая семантика (логический/арифметический/циклический), дисциплина масок, контроль ширины слова и переносимости позволяют решать задачи ЕГЭ быстро и безошибочно: от простых вычислений вида «сдвиг на k» и проверки кратности до аккуратной работы с полями и ротациями. При этом именно формальные инварианты и правила из этого материала превращают «фокусы со сдвигами» в доказуемо корректные решения.