Исследование касается операций арифиметичского и логического сдвига целых чисел в среде 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».