Арифметические действия в различных системах счисления

Когда в школе пишут 9 + 1 = 10, на самом деле разряд единиц заполняется и 1 переходит в разряд десятков. В двоичной системе разряд заполняется быстрее: 1 + 1 = 10₂. Процессор компьютера выполняет все вычисления в двоичной системе — именно по правилу сложения столбиком. На этом уроке перенесём действия столбиком на любое основание: единственное отличие в том, что разряд заполняется не на 10, а на b. Переводить числа мы научились на уроке «Восьмеричная и шестнадцатеричная системы счисления»; теперь будем считать с ними напрямую.

Сложение столбиком: перенос

Сложение выполняется, как в десятичной системе: справа налево, по разрядам. Если сумма s в разряде меньше основания (s < b), её записывают как есть. Если s ≥ b, в разряд пишут s − b, а 1 переносят в следующий разряд. Вся таблица сложения двоичной системы — четыре строки: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 10₂, 1 + 1 + 1 = 11₂.

Почему именно так? Когда в разряде набирается b единиц, вместе они равны ровно 1 единице следующего разряда, ведь вес каждого разряда в b раз больше веса правого соседа. Например, в восьмеричной системе 13 единиц в младшем разряде = 8 + 5: восемь переходят в следующий разряд как 1, а 5 остаётся. Десятичное правило «1 пишем в уме» — это случай b = 10. Ниже двоичное сложение показано столбиком.

   111111 
    101101
+    11011
----------
   1001000

Вычитание столбиком: заём

Если при вычитании верхняя цифра меньше нижней, из соседнего левого разряда занимают 1. В десятичной системе эта единица равна 10, а в системе с основанием b — b единицам: 2 в двоичной, 8 в восьмеричной, 16 в шестнадцатеричной. Если в соседнем разряде 0, занимают из разряда левее, и все нули по пути превращаются в b − 1 — как 1000 − 1 = 999 в десятичной системе.

Умножение и деление

Таблица умножения двоичной системы самая простая: 0·0 = 0·1 = 1·0 = 0, 1·1 = 1. Поэтому двоичное умножение — это сдвиги и сложение: для каждой единицы второго множителя первый множитель записывают со сдвигом влево на соответствующий разряд, затем строки складывают. В других системах умножение столбиком выполняется как в десятичной, только перенос находят делением на b. Деление уголком тоже выполняется как обычно; в двоичной системе каждая цифра частного — 0 или 1. Почему сдвиг — это умножение? При сдвиге на разряд влево каждая цифра попадает в разряд, вес которого в b раз больше, значит, всё число умножается на b.

Выражения с разными основаниями и проверка

В заданиях ГЭЦ часто дают выражение с числами в разных системах и просят ответ в определённой системе. Самый надёжный путь: перевести все числа в десятичную систему, вычислить и перевести результат в нужную систему. Если основания 2, 8 и 16, можно перевести всё в двоичную и сложить там. Проверка выбранного варианта переводом в десятичную занимает минуту и ловит ошибки.

Переполнение n-битной ячейки

Компьютер хранит число в ячейке памяти фиксированной длины. В n битах помещаются числа от 0 до 2ⁿ − 1: в 8 битах — 0…255, в 16 битах — 0…65535. Когда сумма выходит за этот предел, самый левый перенос не помещается в ячейку и теряется — это переполнение. В ячейке остаётся остаток от деления суммы на 2ⁿ, и программа видит неожиданно маленькое число.

В Python int(s, b) переводит запись в системе с основанием b в десятичное число, а bin(), oct(), hex() — обратно, так что любой ответ проверяется парой строк. Целые числа Python не переполняются, поэтому 8-битную ячейку имитируем через % 256:

a = int('101101', 2) + int('11011', 2)
print(a, bin(a))
b = int('3657', 8) + int('1426', 8)
print(b, oct(b))
c = int('A03', 16) - int('4F8', 16)
print(c, hex(c))
print((200 + 100) % 256)

72 0b1001000
2757 0o5305
1291 0x50b
44

На этом уроке основание всегда было известно. На уроке «Системы счисления: задачи с неизвестным основанием» будем решать обратную задачу — находить основание по равенству; именно таковы многие кодируемые задания ГЭЦ.