Информатика · объяснение и практика

Как сдвиг битов связан с умножением и целочисленным делением

Связываем сдвиг целого Python с умножением и делением на степень двойки, проверяем отрицательные числа и не переносим правила на фиксированную разрядность без условий.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта

Главная мысль

Для целых Python сдвиг влево на k неотрицательных позиций равен умножению на 2ᵏ, сдвиг вправо — целочисленному делению на 2ᵏ с округлением вниз. Для отрицательных чисел это не усечение к нулю.

Как двоичная запись показывает масштаб

Число 6 имеет двоичную запись 110. Сдвиг влево на две позиции даёт 11000, то есть 24. К концу записи добавились два нулевых разряда, число умножилось на 4. Это не умножение на 2k: при k = 3 множитель 8, а не 6. Степень связана с разрядной структурой записи.

Для положительного 13 сдвиг вправо на два даёт 3, поскольку 13 // 4 = 3. Младшие разряды, отвечающие остатку 1, не входят в результат. Обратный сдвиг даёт 3·4 = 12, а не 13: остаток 1 потерян. Поэтому сдвиги в противоположные стороны не являются взаимно обратимыми для любых целых входов.

Что происходит с отрицательными числами

В Python −3 >> 1 равно −2, как −3 // 2. Округление идёт вниз к меньшему целому. Результат −1 получился бы от усечения −1,5 к нулю, но это другая операция. Отрицательные входы следует проверять отдельно, потому что положительные примеры не показывают различия двух правил деления.

Python использует произвольную точность целых и определяет побитовые операции через знаковое расширение. У фиксированного знакового или беззнакового типа другого языка правила сдвига, переполнения и больших значений k могут отличаться. Поэтому перенос формулы требует указания языка, типа и допустимого диапазона. Слова «сдвинуть биты» недостаточно для универсального результата в любой программе.

Пример

Чему равно 20 >> 2 для целого Python?

20 // 4 = 5. Двоичная запись 10100 после удаления двух младших позиций даёт 101, то есть 5. Здесь остаток нулевой.

Какие ограничения проверять во вводе

Количество позиций должно быть целым и неотрицательным. Отрицательный шаг сдвига вызывает ValueError в Python. Очень большой левый сдвиг способен потребовать много памяти, хотя фиксированного 32-битного переполнения нет. Для внешнего ввода ограничивают и размер числа, и k, а не только ловят исключение после дорогого вычисления.

Правый сдвиг связан именно с делением на степень двойки и не заменяет деление на 10. Сдвиг маски флагов также может изменить назначение битов, а не просто числовой размер. Нужно решить, рассматривается число или упакованные поля протокола. Оператор может быть корректным по языку, но нарушать контракт данных, если перенёс значение в чужую позицию. Проверка результата должна учитывать и арифметику, и заявленную разрядность представления.

От чтения к действию

А теперь — вы

Чему равно 7 << 2 в Python?

Частые вопросы

Правый сдвиг всегда можно отменить левым?

Нет. Удалённые младшие биты могли содержать ненулевую информацию.

Что даёт −3 >> 1 в Python?

−2, поскольку это деление на 2 с округлением вниз.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться