14.1.Еще пример задания

У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь влево

2. вычти 1

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.

Решение:

1. важно, что числа однобайтовые – на число отводится 1 байт или 8 бит

2. главная проблема в этой задаче – разобраться, что такое «сдвиг влево»; так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса:

бит
переноса

м ожно доказать, что в большинстве случаев результат этой операции – умножение числа на 2, однако есть исключение: если в старшем (7-ом) бите исходного числа x была 1, она будет «выдавлена» в бит переноса, то есть потеряна¹, поэтому мы получим остаток от деления числа 2x на 2⁸=256

1. попутно заметим, что при сдвиге вправо² в старший бит записывается 0, а младший «уходит» в бит переноса; это равносильно делению на 2 и отбрасыванию остатка

2. таким образом, фактически команда сдвинь влево означает умножь на 2

3. поэтому последовательность команд 11221 выполняется следующим образом

   Код команды	Действие	Результат	Примечание
   		104
   1	умножь на 2	208
   1	умножь на 2	160	остаток от деления 208*2 на 256
   2	вычти 1	159
   2	вычти 1	158
   1	умножь на 2	60	остаток от деления 158*2 на 256

4. правильный ответ – 60.

1^ Используя ассемблер (язык машинных кодов с символьными командами), можно добраться до бита переноса и использовать его.

2^ Кроме логического сдвига вправо, о котором идет речь, есть еще арифметический, при котором старший бит не меняется.