Позиционная система представления (счисления) целых без знака

Введенная примитивная система представления целых без знака страдает одним существенным недостатком: очень большое число знаков (единиц) в записи числа. Причем длина записи пропорциональна величине числа.

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

Проделав такое позиционирование, можно представить число в следующем виде:

...((d_3*10+d₂*10)*10+d₁)*10+d₀

Здесь, d₃,d₂,d₁,d₀ - полное число тысяч, сотен, десятков и единиц соответственно.

Мы перешли к алфавитной системе кодирования целого числа без знака, предложенной, как считается, арабами и основанной на следующих принципах:

* вводится конечное, относительно небольшое число знаков - алфавит цифр;

* обозначения строятся как линейные последовательности (цепочки) знаков алфавита.

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

Прежде всего выделим два целых числа без знака, которые играют особую роль: число, обозначаемое как 0, характеризует отсутствие элементов в множестве; число, обозначаемое как 1, характеризует минимально возможное увеличение или уменьшение числа элементов в множестве.

Концепция позиционной В-ичной системы кодирования (счисления) целых чисел без знака заключается в четырех пунктах.

1. Выбирается произвольное, большее единицы, число, которое называется основанием системы счисления и обозначается как B. Числа меньшие B образуют базу системы счисления.

2. Для чисел базы выбираются уникальные обозначения, которые называются цифрами.

3. Любое целое число без знака единственным образом представляется с помощью чисел базы системы счисления и операций сложения - умножения в виде канонического арифметического выражения:

ЗНАЧЕНИЕ_в(цбз) = (d_n-1*B^n-1+d_n-2*B^n-2+...+d₁*B¹+d₀*B⁰)_в.

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

ЗАПИСЬ_в(цбз) = (d_n-1d_n-2...d₁d₀₎)_в

При этом о коэффициенте d_i принято говорить как об i-м разряде числа, а об n - как о количестве разрядов числа. Диапазон чисел 0 ¸ n-1 называется разрядной сеткой числа.

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

В практике вычислений именно такие записи используются для обозначения чисел.

Пример.

Запись числа в 10-й системе [125]₁₀ =

каноническое выражение 10-й системы [1*10²+2*10¹+5*10⁰]₁₀

запись 8-й системы [125]₈ =

каноническое выражение 8-й системы [1*8²+2*8¹+5*8⁰]₈

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

Десятичная система счисления также используется для вычислений при переводе одного и того же числа из одной системы счисления в другую. Прежде всего она используется для представления оснований различных систем счисления:

[10]₂ = 2, [10]₈ = 8, [10]₁₆ = 16.

Существует формула, позволяющая определить число q различных n - разрядных чисел в системе счисления с основанием B:

q = Bⁿ.

Для того чтобы все эти числа выписать, следует воспользоваться простым правилом:

* образуется таблица, состоящая из n столбцов и Bⁿ строк;

* столбцы нумеруются справа - налево: n-1, n-2,...,1, 0;

* в столбце 0 записывается последовательность: 010101;

* в столбце 1 записывается последовательность: 00110011;

* в столбце 2 записывается последовательность: 0000111100001111;

* в столбце i записывается последовательность: .

Так, например, имея в своем распоряжении 3 двоичных разряда, можно записать в них 2³ = 8 различных двоичных числа (Табл. 1.1).

Таблица 1.1 - Правило образования записей трехразрядного двоичного числа

разряды числа

Ниже приведена таблица записей цифр (заштрихованы) и чисел типа целое без знака в различных системах счисления.

Таблица 1.2 - Цифры и числа в различных системах счисления

	Основание системы счисления		Основание системы счисления
Число					Число
Нуль					Восемь
Один					Девять
Два					Десять				A
Три					Одиннадцать				B
Четыре					Двенадцать				C
Пять					Тринадцать				D
Шесть					Четырнадцать				E
Семь					Пятнадцать				F
					Шестнадцать

Любая позиционная система счисления (кодирования) решает проблему обозначения целых чисел без знака:

* любое целое без знака может быть обозначено последовательностью цифр - записью числа;

* записи чисел допускают простые алгоритмы выполнения арифметических операций, например: ЗАПИСЬ (первое слагаемое) + ЗАПИСЬ (второе слагаемое) = ЗАПИСЬ (сумма двух слагаемых).

Запись числа является кодом числа и представляется последовательностью цифр. Позиция цифры в этой последовательности называется разрядом числа. Разряды числа нумеруются справа налево.

Рисунок 1.1 - Позиционная запись числа

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

значение любого числа представляется в виде канонического арифметического выражения (арифметического выражения специфического вида).

Рисунок 1.2 - Каноническое арифметическое выражение

Можно также определить В-ично десятичную систему обозначения чисел. В этом случае цифры В-ичной системы представляются десятичными числами. Например: (AF7)₁₆ ®(10,15,7)_16-10. Следует иметь в виду, что простых алгоритмов выполнения арифметических операций для такой системы не существует