Уравновешенные системы счисления

Системы счисления

Система счисления - способ записи (изображения) чисел.

Символы, при помощи которых записывается число, называются цифрами.

Системы счисления, в которых количественный эквивалент каждой цифры зависит от ее положения (позиции) в коде(записи) числа, называются позиционными.

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

Базисом позиционной системы счисления называется последовательность чисел, каждое из которых задает количественное значение или "вес" каждого разряда.

Например: Базисы некоторых позиционных систем счисления.

Десятичная система: 10⁰, 10¹, 10², 10³, 10⁴,..., 10ⁿ,...

Двоичная система: 2⁰, 2¹, 2², 2³, 2⁴,..., 2ⁿ,...

Восьмеричная система: 8⁰, 8¹, 8², 8³, 8⁴,..., 8ⁿ,...

Совокупность различных цифр, используемых в позиционной системе счисления для записи чисел, называется алфавитом системы счисления. Количество цифр в алфавите равно основанию системы счисления.

Уравновешенные системы счисления

---===---

Двоичная СС с большим успехом используется в компьютерной технике

до сих пор. Однако выявились и существенные недостатки использования

двоичной СС, влияющие на скорость работы процессора и надежность передачи

информации.

Одним из этих недостатков является так называемая проблема представления

отрицательных чисел. Попытка преодолеть этот и другие недостатки двоичной

системы счисления стимулировала использование в компьютерах других систем

счисления и развитие собственно теории систем счисления.

Выбирая систему кодирования информации в компьютере, разработчики в

первую очередь думают о быстродействии процессора, т.е. о скорости обработки

закодированной информации.

///

Что привычно и хорошо для человека, выполняющего вычисления на бумаге,

не всегда хорошо для компьютера. Для того чтобы сложить два целых числа

с разными знаками, и человек, и компьютер, вообще говоря, должны выполнить

следующие действия:

1) взять модули слагаемых;

2) сравнить эти модули;

3) запомнить знак большего по модулю слагаемого;

4) получившийся результат з

5) из большего модуля вычесть меньший модуль;

6) записать со знаком из п. 3.

Многовато будет для простой и часто используемой операции!

\\\

В десятичной системе счисления для представления отрицательных чисел

человек использует знак числа. То, есть для записи отрицательных чисел

имеющихся 10 знаков недостаточно. Используется еще один знак - '-'.

То есть для записи отрицательных десятичных чисел потребоваломь 11 знаков!

Аналогично, для записи отрицательных двоичных чисел требуется 3 знака,

но в нашем распоряжении их два - 0 и 1. Для решения проблемы вначале века

использовалось прямое кодирование: в старший бит регистра числа явно

вписывался знак '0' для положительных и знак '1' для отрицательных чисел.

При определении значения числа этот бит игнорировался. Вроде бы все

нормально, но процессор не может работать с отдельными битами регистра.

Для определения знака числа, число загружалось в процессор, применение

маски (числа 10 или 1000) оставляло в регистре только бит знака, весь

регистр проверялся (ноль или нет). Для выделения значения числа снова

использовалась маска (7F или 7FFF), после чего определялось число -

не слишком ли много действий процессора для выполнения простых операций?

///

для 1 байта 5 = 00000101 -5 = 10000101

\\\

Чтобы сократить число действий процессора, придумали обратный код:

для чисел договорились старший бит не использовать, а для получения

отрицательного числа выполнять команду инвертирования - менять в записи

0 на 1, а 1 на 0. Это одна команда для процессора. Но проверка бита

знака все равно остется.

///

для 1 байта 5 = 00000101 -5 = 11111010

\\\

Кроме всего прочего применение прямого или обратного кодирования

добавляет новую проблему: число 0 оказываеися можно хранить двумя

разными способами (как?). Появились значения +0 и -0.

Представьте, решаем квадратное уравнение, и начинаем проверять,

равен ли он 0. Поребуется сравнивать как с число 0, так и с числом -0,

- двойная работа!

Использующийся в настоящее время во всех компьютерах способ хранения

отрицательных чисел называется "дополнительный код". Для получения из

положительного числа отрицательного, как и при дополнительном коде,

выполняют инвертирование, после чего к результату добавляется 1.

Неболбьшое усложнение кодирования снимает проблему двойного представления

нуля:

00000000 - исходное

11111111 - после инвертирования

----------

100000000 - после добавления 1

Так как самый старший бит является девятым и в однобайтный регистр не

помещается, он будет отброшен. То есть 0 представляется только как 00000000.

Кодирование называется дополнительным, потому что положительное и

отрицательное числа "дополняют" друг друга до той самой единицы, бит для

хранения которой выходит за пределы регистра. Поэтому и преобразование

отрицательного числа в положительное происходит по тому же правилу:

инверсия и увеличение на 1.

Еще одно преимущество такого представления чисел: появилась возможность

отказаться от операции вычитания. Вместо нее применяется сложение с

отрицательным числом.

Попробуйте выполнить сложение над двоичными числами, записанными в

дополнительном коде.

///

!!! подобрать примеры сложения положительных, отрицательных, смешанных чисел!!!

\\\

Все вроде хорошо, но попробуйте в переменную X, объявленную как

var x:integer;

записать положительное число 37000, хранимое без знака (как word),

получим, неожидано, отрицательный результат -28536!

Подобные фокусы могут привести к ошибочной интерпретации результатов

работы программы.

///

var x:integer; y:word;

begin

y:=37000; x:=y; writeln(x); readln;

end.

\\\

Ошибка произошла потому, что типы integer и word по разному понимают

содержимое старшего бита регистра.

---===---

Троичная система

Можно ли записывать целые отрицательные числа без знака, но и без

дополнительного кодирования?

Можно! Например, в любой P-ичной уравновешенной системе счисления.

Уравновешенная система с наименишим основанием - это троичная.

В 60-х годах XX столетия в МГУ им. М.В. Ломоносова была создана

троичная ЭВМ "Сетунь", запущенная потом в серию. Для кодирования информации

в этой машине использовалась троичная уравновешенная система счисления,

вместо бита использовался трит, вместо привычной двоичной логики - троичная.

Разработчик этой ЭВМ Николай Петрович Брусенцов.

Quot;бит" - место для хранения двоичной цифры - 0 или 1, "трит" - место для хранения цифры троичной системы счисления.   Троичную систему счисления можно построить, как и другие, взяв за основание число 3. Базой при этом будут числа 1, 3, 9, 27, 81,..., а цифрами (алфавитом) 0, 1 и 2. Но кто нам мешает в качестве цифр взять символы { a, 0, 1}, где a равно -1. Глядя на набор цифр, понятно, почему эту систему назвали уравновешенной, или симметричной. Количество цифр до цифры 0 такое же ("уравновешено с"), что количество цифр после цифры 0. "Уравновесить" можно любые системы счисления с нечетным основанием.   Десятичное число Число в троичной уравновешенной системе положительное отрицательное положительное отрицательное 1 -1 1 a 2 -2 1a a1 3 -3 10 a0 4 -4 11 aa 5 -5 1aa a11 6 -6 1a0 a10 7 -7 1a1 a1a   Очевидно, знак для представления отрицательных чисел в урвновешенных системах счисления не нужен! Если у нас есть хотя бы трицифры, обязательно 0, обязательно 1, для третьей цифры можем ставить в соответствие отрицательное значение (-1). Можно ввести отрицательные значения для некотрых цифр СС с четным основанием, но это приводит к тому, что некоторые числа можно будет записать разными способами. /// Для "четверичной" системы счисления можно выбрать и {-1, 0, 1, 2}, и {-2, -1, 0, 1}. \\\   ---===---   Рассмотрим операции сложения и вычитания в троичных системах:   в троичной системе Сложение   + 0 1 2 0 0 1 2 1 1 2 10 2 2 10 11   Умножение   * 0 1 2 0 0 0 0 1 0 1 2 2 0 2 11     в троичной уравновешенной системе сложение + 1 0 1 1 11 1 0 0 1 0 1 1 0 1 11   умножение * 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1     /// сформировать правила построения таблиц сложения и умножения и правила арифметических операций для целых чисел. \\\ ЧислаФибона́ччи — элементы числовой последовательности, где каждое следующее число образуется суммой двух перед ним стоящих чисел (кроме первых двух).