О системах счисления
А.Д. Смирнов
Со школьной скамьи мы привыкли пользоваться как для счета, так и для вычислений позиционной десятичной системой счисления. Нуль и первые девять целых чисел обозначены знаками: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, называемыми цифрами. Десять обозначается двумя цифрами: единицей и нулем, и называется основанием системы.
Каждая цифра в числе имеет свой вес в зависимости от той позиции (места), на которой она стоит. Вес единицы в каждой позиции является степенью числа — основания системы. Действительно, 100 — это 102; 10=101; 1=100; 0,1=10-1 и т. д. Веса всех позиций мы помним на память, поэтому просто пишем 251,9, а не 2в102+5в101+1в100+ 9в10-1. Чтобы производить арифметические действия над числами, мы должны знать таблицу сложения и таблицу умножения для первых девяти чисел.
Десятичная позиционная система очень удобна для вычислений, производимых вручную, поэтому она вытеснила другие системы и содействовала успешному развитию математики. Следы других, ранее применявшихся систем остались в некоторых мерах веса, длины, в измерении времени, углов и для обозначения часов суток или летоисчисления.
Но попробуйте произвести арифметические действия в этих системах счисления, — например сложить 37 и 97 в римской системе вычисления: XXXVII+XCVII, или из 1 версты 457 сажен 1 аршина 1 вершка вычесть 490 сажен 2 аршина 15 вершков, — как вы сразу почувствуете всю непригодность непозиционных систем или систем с разными основаниями для проведения арифметических действий.
Хотя для ручного счета и вычислений с помощью механических счетных машин десятичная позиционная система оказалась наилучшей, ее применение в электронных машинах вызывает много трудностей.
Дело в том, что в ней слишком много цифр. Каждый разряд счетчика или запоминающего устройства, независимо от того, построены ли они на механическом принципе действия, на электромагнитном или на электронном, должен принимать 10 различных состояний для изображения цифр от 0 до 9.
В механическом счетчике дело обстояло просто: цифровое колесо делилось по окружности на 10 частей и каждой цифре соответствовал угол поворота цифрового колеса. В электронных и электромагнитных устройствах это осуществить труднее.
Но ведь основание десять не единственное возможное основание для позиционной системы счисления. Меньше всего цифр потребуется в системе счисления, за основание которой принято число два.
В двоичной позиционной системе счисления потребуются только две цифры, 0 и 1, вместо 10 цифр в десятичной системе. Каждая цифра в числе в зависимости от ее положения (позиции) будет умножаться на определенную степень двух, подобно тому как в десятичной системе каждая цифра умножалась на определенную степень десяти (одну десятую, десять, сто, тысячу и т. п.). Запись в двоичной системе числа 10110,1 означает (для отличия чисел двоичной системы от десятичной первые будем давать жирным шрифтом): 1в24+0в23 + 1в22+1в21+0в20+1в2-1=16+4+2+1/2=22, 5; число 5, которое можно представить в виде 5 =4+1 = 1в22+1в20, записывается, следовательно, как 101.
Запись чисел в двоичной системе легко представить себе следующим образом. Возьмем счеты, у которых в каждом разряде вместо десяти костяшек всего две. Будем откладывать на этих счетах подряд целые числа, начиная с единицы. Единица отложится как обычно. Отложив два, мы уже используем две костяшки, следовательно, их нужно сбросить и сделать перенос, отложив 1 в следующем втором разряде. Число два будет записано как 10, число три — как 11, и т. д. Приведем для примера несколько чисел, записанных в двоичной системе:
1 — один
1011 — одиннадцать
10 — два
1100 — двенадцать
11 — три
1101 — тринадцать
100 — четыре
1110 — четырнадцать
101 — пять
1111 — пятнадцать
110 — шесть
10000 — шестнадцать
111 — семь
0,1 — половина
1000 — восемь
0,01 — четверть
1001 — девять
0,001 — восьмая
1010 — десять
0,11 — три четверти
Основное преимущество применения двоичной системы в математических машинах состоит в том, что довольно легко создать счетчик, имеющий всего два фиксированных состояния в каждом разряде. Кроме того, оказалось очень просто изображать двоичные цифры при помощи импульсов. Наличие импульса соответствует 1, отсутствие импульса — 0. Запоминать двоичные цифры также легко, например: намагничен участок магнитофонной ленты — это значит, что запоминается 1, не намагничен этот участок — запоминается 0.
Арифметические действия в двоичной системе счисления очень просты.
Таблица умножения выглядит так:
0в0 = 0; 1в0 = 0; 0в1 = 0; 1в1 = 1.
А таблица сложения так:
0 + 0 = 0; 1+0=1; 0+1 = 1; 1 + 1 = 10.
Сложим, например, 2 и 3, для чего запишем числа одно под другим:
10 + 11 ---- 101
Начнем сложение с младших разрядов. 1+0=1; 1+1=2, но два — это единица в следующем старшем разряде, поэтому запишем нуль и перенесем 1 в старший разряд, подобно тому как при сложении 8 и 2 мы пишем 0, а десять переносим в виде единицы в старший разряд. Получилось число 101, т. е. 5.
Умножить одно число на другое тоже просто. Когда в разряде множителя стоит 1, множимое переписывается без изменения, когда 0 — умножения вообще не происходит и нужно переходить к следующему разряду множителя, не забывая сдвигать частичные произведения влево на соответствующее число разрядов.
Умножим, например, 6-5. Шесть в двоичной записи — это 110, а 5 — 101.
110 * 101 110 110 ------ 11110
Следовательно, умножение свелось к переписи множимого в соответствующих разрядах и сложению. Получилось число, которое мы сможем расшифровать так:
1в24+1в23+1в22+1в21+1в20=16+8+4+2=30.
Деление сведется к последовательному вычитанию делителя из делимого и анализу остатка. Если остаток положителен, в частном записывается единица, а делитель сдвигается вправо; если остаток отрицателен, в частном записывается нуль, восстанавливается уменьшаемое, делитель опять же двигается вправо.
Проследим это на примере: 15:3. Изображение пятнадцати в двоичной системе — это 1111, а трех — 11.
1111|11 - |--- 1100|101 ----- 0011 - 11 ----- –0011 – отрицательный остаток 0011 – восстанавливаем предыдущее значение - 11 ----- 0000
Следовательно, деление свелось к вычитанию делителя из соответствующих разрядов делимого и обратному прибавлению его, если получается отрицательный результат.
А как же учесть знаки чисел при умножении и делении? Сделать это, оказывается, просто. Возьмем для учета знаков одноразрядный счетчик. Минус обозначим через 1, а плюс — через 0. Для определения знака произведения или частного достаточно сложить знаки сомножителей или знаки делимого и делителя. Проверим результаты:
+ на + дает + 0+0 = 0, т. е. +
+ на - дает - 0+1 = 1, т. е. -
- на + дает - 1+0 = 1, т. е. -
Более подробно рассмотрим случай, когда оба сомножителя или и делимое и делитель имеют знак “-”. Будем складывать 1+1. В двоичной записи это будет 10, но так как счетчик знака имеет всего один разряд, то в нем окажется цифра младшего разряда, т. е. 0, а единица переноса в старший разряд пропадет. Следовательно, и в этом случае получается правильный результат:
- на - дает + 1 + 1 = 1, т. е. +.
Мы убедились, что все четыре действия арифметики в двоичной системе свелись в конечном итоге к сложению и вычитанию. А нельзя ли и вычитание заменить сложением?
Оказывается можно, но только в том случае, если отрицательные числа записывать в специальном виде: вместо единиц писать нули, а вместо нулей — единицы. Такая форма записи называется обратным кодом.
Если ввести некоторые дополнительные элементы в арифметическое устройство и представлять отрицательные числа в обратном коде, то вычитание двух положительных чисел можно заменить их сложением, записав вычитаемое в обратном коде.
Все действия в двоичной системе нам удалось в конечном итоге свести к сложению и замене кодов на обратные. Простота арифметических действий в двоичной системе и наличие в ней всего двух цифр, 0 и 1, делают ее наиболее удобной для применения в электронной машине.
Но мы привыкли иметь дело с десятичными числами. Перевод их в двоичную систему весьма трудоемок, точно так же как и обратный перевод результатов из двоичной системы в десятичную. Выполнение этой задачи возложили на саму машину. По специальной программе она выполняет эти переводы, а чтобы десятичные числа можно было ввести в машину, каждую цифру десятичного разряда изображают четырьмя двоичными разрядами.
Число 15 запишется в такой десятично-двоичной форме как 0001 0101, а уже в машине оно переведется в чисто двоичную форму 1111. Результат вычислений сначала переводится в десятично-двоичную форму, а потом печатается в чисто десятичной системе.
Некоторые машины считают прямо с числами, представленными в десятично-двоичной форме. Арифметическое устройство таких машин значительно сложнее, зато не требуется перевода чисел в двоичную систему и обратно.
Глава из книги “Современные математические машины”, М., 1959 г., стр. 58.
Перепечатывается с разрешения автора.
