Позиционные и непозиционные системы счисления

Конструкция вычислительных машин и программирование на них тесно связаны с системами счисления. Система счисления – это совокупность приемов наименования и записи чисел. Условные знаки, применяемые при записи чисел, называются цифрами.

Все системы счисления делятся на две группы: позиционные и непозиционные. Непозиционной называется такая система, у которой количественное значение цифры зависит от ее начертания и не зависит от положения, т.е. каждый знак всегда изображает одно и то же число. Примером такой системы счисления может служить римская система счисления. В этой системе запись различных целых чисел производится с помощью следующих цифр:

I V X C D M и т.д.

1 5 10 50 100 1000

Для записи больших цифр в римской системе введенных знаков будет не хватать, и нужны новые. И сколько бы мы их не вводили, всегда можно придумать число, которое уже введенными знаками изобразить трудно. Римская система счисления не используется в вычислениях. Ее применяют обычно для обозначения месяцев, веков, глав и т. п. Большинство систем счисления относятся к позиционным. В них значение каждой цифры изменяется в зависимости от места (позиции), на котором она находится. Общепринятой системой счисления является десятичная позиционная система, берущая свое начало от счета на пальцах. Она была изобретена в Индии, затем заимствована арабами и уже через арабские страны пришла в Европу.

В различные исторические периоды человек использовал позиционные системы счисления, отличные от десятичной. Так, в Древнем Вавилоне (2000 лет до н. э.) применялась шестидесятичная система счисления. Эта система счисления применяется до сих пор при измерении углов, времени, а именно: остатки ее мы находим в делении часа на 60 минут, а минуты на 60 секунд, круга на 360 градусов, т.е. 6 раз по 60. Возникновение шестидесятичной системы счисления связано со слиянием в одно государство двух древних народов – сумерийцев и аккадян. Во вновь образованном государстве остались в ходу единицы веса, используемые ранее тем и другим народами, причем одна из этих единиц была приблизительно в 60 раз больше другой.

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

Число 12 люди считают магическим с тех пор, когда они научились считать. На нем построены системы измерения и летосчисления, по нему ориентируются календари, оно входит во многие пословицы.

Каждый знает: год делится на 12 месяцев. Но, кроме того, существуют 12 апостолов, 12 знаков зодиака и 12 разбойников. Изучавшие математику называют 12 «поцелуйным числом третьего измерения». Если вокруг шара расположить еще 12 шаров того же диаметра, то каждый из них математически «поцелуется» с центральным, то есть коснется его в одной точке.

Почему число 12 играет такую роль в истории нашей цивилизации? Одна из наиболее важных причин – календарь, дающий возможность рационально разделить год на составные части. Это связано с полнолунием, которое мы наблюдаем на небе 12 раз в году. К тому же и круг с помощью циркуля и линейки можно разделить на 6 (а тем самым на 12) равных частей. Использование числа 12 в качестве базового значительно облегчало счет.

Даже античные жители Израиля, упрямо признававшие из 12 заповедей только 10, не могли полностью освободится от магии дюжины. У мудрого Иакова было 12 сыновей, которые стали основателями 12 колен Израиля. Иисус Навин в знак благодарности за удачную переправу через Иордан велел воздвигнуть там 12 каменных глыб. Купель Соломона окружали 12 бронзовых быков, а на груди у главного священника сверкало 12 драгоценных камней. В свою очередь, у Иисуса было 12 верных слуг. В Апокалипсисе от Иоанна у небесного Иерусалима 12 ворот. Он стоит на 12 камнях, на которых высечены имена 12 апостолов. Римские законы были записаны на 12 бронзовых дощечках. Со времен Древнего Рима повелось назначать 12 присяжных при судебных разбирательствах.

Древние китайцы, наблюдавшие за ночным небом, тоже делили год на 12 лун и создали соответствующую астрологию. Больше других европейцев к числу 12 оказались привержены англичане, с большим трудом перешедшие за десятичную систему, да и то не во всем. И только древние германцы, жившие в лесах и мало смотревшие в небо, в меньшей степени уверовали в магию дюжины. Хотя и в немецком языке само это слово появилось не случайно. И, наконец, 12 занимает почетное место в играх, например, в лото. Словом, счастливым числом его считают вполне заслуженно.

Встречались, например, в древнем Китае, пятеричная система счисления. У населявших американский континент народностей – ацтеков и майя была распространена двадцатеричная система счисления. Кроме названных систем, цивилизации известны и другие.

Чтобы различать, в какой системе счисления записано число, рядом с числом в виде индекса (в десятичной системе) указывается основание системы счисления. Например, 257₁₀ – записано в десятичной системе счисления, а 257₈ – в восьмеричной. Указание основания опускается в тех случаях, когда основание используемой системы не вызывает сомнений.

Принцип построения позиционных систем проще всего проиллюстрировать на примере десятичной системы счисления. В этой системе для записи любых чисел используется десять различных символов (цифр): 0,1,2,...,9. С помощью одной цифры можно изобразить самое большее число – 9. Число на единицу большее, чем 9, уже записывается двумя цифрами – 10. Затем младший разряд возрастет до максимальной цифры (число 19). После чего добавляется единица к следующему разряду, а в младшем разряде снова 0 (20) и т.д. Дойдя до числа 99, т.е., имея в обоих разрядах максимальную цифру, мы записываем 1 в новом, более старшем разряде, а в обоих младших – нули (100). Точно такую же процедуру можно использовать и для случая, когда количество используемых цифр меньше десяти.

Итак, введя для числа «десять» обозначение «10», мы не ввели никаких новых символов (цифр), а использовали уже имеющиеся. Однако введением этого обозначения сделан важный шаг в построении системы счисления, а именно: значение каждой из цифр поставлено в зависимость от того места, где она стоит в изображении числа.

Пример. В записи числа 141,14 единица, стоящая слева на первом месте, означает количество сотен; единица, стоящая перед запятой, – количество единиц; а единица, стоящая после запятой, – количество десятых долей, содержащихся в числе. Последовательность цифр 141,14 представляет собой сокращенную запись выражения:

141,14 = 1·100+4·10+1+1:10+4:100.

Количество различных цифр, используемых в позиционной системе счисления для изображения произвольных чисел, называется основанием системы счисления. Основанием десятичной системы счисления является число десять. То есть в десятичной системе для записи числа употребляются десять цифр: 0,1,......, 9; а в пятеричной системе счисления достаточно пяти цифр: 0,1,2,3,4. Основание пятеричной системы счисления число пять – изобразится в ней как «10», поскольку оно является единицей следующего (второго) разряда. Так будет в любой системе счисления: основание системы счисления в любой системе записывается как 10. Позиции, на которых в последовательности стоят цифры, перенумерованы. Эти позиции называются разрядами числа. Каждой цифре рассмотренной последовательности приписано определенное значение. Цифра, стоящая в некотором разряде, имеет значение большее того, которое она бы имела в разряде с номером, меньшим на единицу, во столько раз, каково основание системы счисления. Цифра, стоящая в нулевом разряде, имеет своим значением соответствующее число из основания.

Умножение числа на основание системы счисления сводится к переносу запятой на один разряд вправо, а деление на основание системы – к переносу запятой на один разряд влево.

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

257 = 200+50+7.

Любое число в позиционной, в том числе и в десятичной системе, записывается в виде последовательности цифр, разделенных запятой на целую и дробную части. Такая запись числа есть сокращенная запись. Возьмем, например, число А = 627,3. В развернутом виде оно запишется так:

А₁₀ = 6·102+2·101+7·100+3·10-1.

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

а_n·10n+а_n-1·10n-1+...+а₀·100+а_-1·10-1+...,

где а – одна из цифр 0,1,2,.....,9.

В двоичной системе счисления любое положительное число можно записать аналогично:

А₂=а_n·2n+...+а₀·20+а_-1·2-1+...+а_-m·2-m,

где а – принимает значения 0 или 1.

Запись произвольного числа А в позиционной системе c данным основанием p будет выглядеть так:

А_p=а_n·pn+...+a₀·p0+a_-1·p-1+...+а_-m·p-m.

Как и в десятичной системе, число А_p можно записать в сокращенном виде:

А_p=a_na_n-1...a₁а₀,a_-1...a_-m.

Эта последовательность цифр и будет являться изображением числа А в p-ичной системе счисления.

Если А_p – число, записанное в p-ичной системе счисления, тогда под преобразованием этого числа в q-ичную систему понимают запись числа А последовательностью цифр q-ичной системы.

Подводя итоги, можно сказать, что позиционная система счисления – это способ представления чисел, при котором вклад, вносимый каждой цифрой зависит от ее численного значения и разряда, который она занимает в числе. Обычно этот вклад определяется как произведение значения цифры на некоторое число, определяемое разрядом, – вес разряда. Позиционная система счисления с заданным основанием – это позиционная система, в которой веса являются степенями некоторого числа – основания.