Исследование работы битовых сдвигов

Исследование работы битовых сдвигов в языке Оберон

Исследование касается операций арифиметичского и логического сдвига целых чисел в среде Project Oberon 2013. Оно может представлять интерес для разработчиков компиляторов языков программирования высокого уровня, в частности языка Оберон.

Рис. 1. Выдержки из сообщений о языке Оберон (от 2016 г.) и Оберон-2, касаемо встроенных функциональных процедур.

Было проведено исследование работы операций ASR и LSL в эмуляторе Project Oberon[*]. Для этого был написан небольшой модуль (см. Рис. 2, слева).

ASR — арифметический сдвиг вправо (сохраняет знак числа).
LSL — логический сдвиг влево.

Рис. 2

Очевидно, ASR(x, 33) воспринимается в данной реализации как ASR(x, 1), т. к. второй параметр n берётся по модулю 32. Отсюда ASR(17, 33) = 8 = ASR(17, 1) = 17 DIV 2

Число -2 в дополнительном коде выглядит так:
11111111111111111111111111111110
ASR(n, -2), вероятно, воспринимается как — в двоичном коде — ASR(n, 11110), то есть ASR(n, 30).
Отсюда ASR(17, -2) = 0 = ASR(17, 30) = 17 DIV (2^30)

Отметим, что (-2) MOD 32 = 30,
(-2) DIV 32 = -1
т. к. (-1) * 32 + 30 = -2
и 0 <= 30 < 32

LSL(17, -2) = 1073741824 = 2^30

И действительно, LSL(17, 30) = 2^30, т. к. число 17 в двоичном виде имеет две единицы: 00000000000000000000000000010001. При сдвиге влево на 30 разрядов старшая из двух единиц теряется. 100 ← 01000000000000000000000000000000 = 2^30

Вывод: множество корректных значений вторых параметров процедур ASR и LSL ограничено промежутком [0; 31].

Логический сдвиг вправо (LSR) отсутствует среди встроенных в язык Оберон функциональных процедур, но может быть реализован с помощью операции MOD или с помощью операций над множествами, такими как разность и пересечение.

На Рис. 3 представлена реализация процедуры LSR с помощью операции взятия остатка от деления нацело (MOD). В двух последних строках на Рис. 4 указаны результаты работы LSR с положительными и отрицательными первыми аргументами. Результаты соответствуют ожидаемым. Деление на нуль исключено строением программы.

Рис. 3

Рис. 4

Но деление на произвольное число — операция затратная, поэтому была произведена попытка реализовать процедуру LSR с помощью операции вычисления разности множеств, которая на ЭВМ реализуется как поразрядное И-НЕ (см. Рис. 5 и 6).

Рис. 5

Рис. 6

Оказалось, что в случае реализации LSR через разность множеств неправильно работает нулевой сдвиг. Обратите внимание, что LSR(-17, -2) не должен выдавать правильный результат, т. к. число -2 не является допустимым значением второго аргумента. Этот процедурный вызов добавлен для полноты картины.

Сдвиг на нуль не работает, потому что при n = 0, 32 - n = 32, а выражение {32..31} является некорректным, т. к. 32 интерпретируется как 0. Т. е. {32..31} = {0..31}. Как следствие, в возвращаемом ASR значении снимаются все биты и ответ получается 0, вместо желаемого -17 (x).

На Рис. 7 представлена быстрая и корректная реализация LSR через пересечение множеств. Результаты испытания процедуры представлены на Рис. 8.

Рис. 7

Рис. 8

Финальный вид программы на Рис. 9.

Рис. 9

Наконец, отметим, что ASR(n, x) = LSR(n, x) при n ⩾ 0.

* Эмулятор ЭВМ Project Oberon 2013. Был использован образ «Full Disk Image».