Представление и обработка чисел в компьютере

Система счисления - это правило записи чисел с помощью заданного набора специальных знаков - цифр.

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

Пусть р - основание системы счисления.
Тогда любое число Z, удовлетворяющее условию Z < pk (k ≥ 0, целое), может быть представлено в виде многочлена со степенями р:

aj - целые числа, удовлетворяющие условию:
значение р = 2 - является минимальным для позиционных систем. Система счисления с основанием 2 называется двоичной.

4.2. Представление чисел в различных системах счисления
4.2.1. Перевод целых чисел из одной системы счисления в другую
Zp → Zr → Zq
r – основание, для которого арифметические операции выполнить легко.
r =1 и r = 10
т.е. перевод осуществляется через унарную или десятичную систему счисления.

Преобразование Zp → Z1 → Zq
Пусть Zq= 0; из числа Zp вычтем 1 по правилам вычитания системы р,
ZP: = ZP – 1
Добавим ее к Zq по правилам сложения системы q,
Zq:= Zq + 1
Повторять пока не достигнем Zp = 0.

Пример 4.1 Выполнить 223 → Z6.
223 = 126.

Преобразование Zp → Z10 → Zq
Z10 → Zq
целочисленно разделить исходное число (Z10) на основание (q) и найти остаток от деления;
частное от деления снова целочисленно разделить на q; процедуру продолжать до тех пор, пока частное от деления не окажется меньше q;
образовавшиеся остатки, записать в обратном порядке;

Zp → Z10
Необходимо Zp представить в форме многочлена и выполнить все операции по правилам десятичной арифметики.
Пример 4.3
Выполнить преобразование 4435 → Z10

4.2.2. Перевод дробных чисел из одной системы счисления в другую
Правильную дробь в исходной системе счисления р будем записывать в виде
0,Yр
Дробь в системе q
0,Yq
Преобразование: 0,Yp → 0,Yq.

0, Yp → 0,Y10 → 0,Yq
Перевода 0,Y10 → 0,Yq
умножить исходную дробь в 10-ной системе счисления на q, выделить целую часть
для оставшейся дробной части операцию умножения повторять, пока в дробной части не окажется 0 или не будет достигнута желаемая точность конечного числа (exact);
записать дробь в виде последовательности цифр после ноля с разделителем в порядке их появления.

Пример 4.4.
Выполнить преобразование
0,37510 → 0,Y2
Таким образом, 0,37510 = 0,0112.

Перевод 0,Yp → 0,Y10,
Сводится к вычислению значения многочлена в десятичной системе счисления.

Пример 4.5
Выполнить преобразование
5,3(3)10 → Х3.
Ответ: 5,3(3)10 = 12,13.

4.2.3. Понятие экономичности системы счисления
Число в системе счисления р с k разрядами, будет иметь наибольшее значение, если все цифры числа окажутся максимальными, т.е. равными р - 1.

Количество разрядов числа при переходе от одной системы счисления к другой в общем случае меняется.
Если р = qσ (σ - не обязательно целое), то (Zp)max = pk - 1 = qσk - 1.
Количество разрядов числа в системах счисления р и q будут различаться в σ раз.

Сравним количество цифр в числе 9910 и его представлении в двоичной системе счисления: 9910 = 11000112; т.е. двоичная запись требует 7 цифр вместо 2 в десятичной
σ = ln(10)/ln(2) = 3,322;
2*3,322 = 6,644 = 7.

Экономичность системы счисления -количество чисел, которое можно записать в данной системе с помощью определенного количества цифр.
Пусть имеется 12 цифр. Можно разбить их на 6 групп по 2 цифры («0» и «1») и получить шестиразрядное двоичное число.
Общее количество таких чисел, равно 26.

наиболее экономичной оказывается троичная система счисления

Пусть имеется n знаков для записи чисел, р - основание системы счисления.
Количество разрядов числа k = n/р,
N - общее количество чисел которые могут быть составлены.

получаем ln p = 1, или р = е,
е = 2,71828..
Ближайшее к е целое число 3
Троичная система счисления оказывается самой экономичной для представления чисел.

4.2.4. Преобразование нормализованных чисел
Вещественное число X может быть представлено в двух формах - естественной и нормализованной.
Число Х10 называется нормализованным, если оно представлено в виде
Х10 = ± M10 ∙ 10±k.

М10 - мантисса нормализованного числа.
Значения мантиссы лежат в интервале
0,1 ≤ М10 ≤ 1;
k - порядком нормализованного числа, это целое положительное десятичное число.

Примеры:
-123410 = -0,1234∙104
0,0345610 = 0,3456∙10-1.
!!!! Нормальное представления числа, мантисса лежит в интервале
1 ≤ M10 < 10,
например, kN = 2,38∙10-2.

Нормализованная форма числа в произвольной системе счисления р:
р-1 ≤ Мр < 1
Для р = 2:

В компьютере все вещественные числа хранятся и обрабатываются в нормализованном двоичном представлении
при их вводе осуществляется перевод
Х10 → Х2,
при выводе обратный перевод
Х2 → Х10.

Пример 4.8
16,510 → X2.
Отдельно целую и дробную части
1610 = 100002,
0,510 = 0,12
16,510 = 10000,12
Нормализуем
10000,12 = (0,100001∙2101)2.

Пример 4.9
(0,11∙2110)2 → Х10
0,112 = 0,7510
(2110)2 = (26)10 = 64
(0,11∙2110)2 = 0,75∙64 = 4810.

4.3. Кодирование чисел в компьютере и действия над ними
4.3.1. Кодирование и обработка в компьютере целых чисел без знака

Для записи числа выделяется фиксированное количество двоичных разрядов.
Память компьютера имеет байтовую структуру.
Размер одной адресуемой ячейки обычно составляет несколько байт.
Например, в компьютерах IBM ячейка памяти объединяет 2 байта (16 двоичных разрядов) - такая комбинация связанных соседних ячеек, обрабатываемая совместно, называется машинным словом.

Пусть количество разрядов k и p = 2
тогда,
(Z2)max = 2k - 1.
при k = 16
(Z2)max = 216 - 1 =
=1111111111111112 = 6553510.

Число 65636 и более в компьютере не может существовать!!!
Минимальным целым числом в беззнаковом представлении, является
(Z2)min = 0000000000000002 = 010.

В языке программирования PASCAL целые числа без знака, для записи которых отводится 2 байта, определены как тип Word.
Тип устанавливает способ кодирования числа, количество отводимых для записи ячеек памяти (т.е. разрядность числа), а также перечень допустимых операций при обработке.

Выход за границу 65535 возможен только путем увеличения количества разрядов для записи числа.
Необходим новый тип со своим Zmax;
Тип Longint с максимальным значением 214748364710, числа которого занимают 4 байта.

4.3.2. Кодирование и обработка в компьютере целых чисел со знаком
1. Прямой код.
Один (старший) разряд машинного слова отводится для записи знака числа;
знак «+» - -1
знак «-» - - 0

Остается 15 двоичных разрядов, что обеспечивает наибольшее значение числа
Zmax = 215 - 1 = 3276710.
Однако его применение усложняет порядок обработки чисел !!!

Пример 4.10
159410 + 1756310 при беззнаковой двоичной кодировке и 16-битном машинном слове.

Пример 4.11 – переполнение типа!
Найти сумму 6553410 + 310

2. Дополнительный код
Ось целых положительных чисел,
(0 ÷ 65535),
сместим положение «О» на середину,
числа, попадающие в первую половину
(0÷32767) -- положительные
(32768 ÷ 65535) -- отрицательные.

Пример
1000000000000012 = 3276910 – код отрицательного числа.
0000000000000012 = 110 - код положительного числа.
Старший бит - у кодов положительных чисел «0», отрицательных - «1».

Способ построения дополнительного кода целых чисел
Дополнением (D) k-разрядного целого числа Z в системе счисления р называется величина
D(ZP, k) = pk - Z.

Дополнительный код (DK) двоичных целых чисел строится по следующим правилам:
для положительных Z2 ≥ 0 дополнительный код совпадает с самим числом
DK = Z2
для отрицательных Z2 < 0 дополнительный код совпадает с дополнением модуля числа
DK = D(|Z2|,k).

Пример 4.14
Построить дополнительные двоичные коды чисел (а) 310 и (b) -310.

в 2-байтном машинном слове интервал чисел
[-32768; 32767] - типа Integer в языке PASCAL.
Перевод в дополнительный код происходит автоматически при вводе чисел; в таком виде числа хранятся в ОЗУ и затем участвуют в арифметических операциях.

Операция вычитания двух чисел как самостоятельная отсутствует - она заменяется сложением первого числа с дополнительным кодом второго.
Пример. Найти значение (27-3)10 в двоичной кодировке.

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

Основная форма представления кодов вещественных чисел - двоичная нормализованная.
Записываются и хранятся в памяти все составляющие нормализованной формы (знак числа, мантисса, знак порядка и порядок).
Например, типа Real («вещественный») из языка PASCAL размещаются в 6 байтах, т. е. 48 двоичных разрядах.

Поскольку значение мантиссы лежит в интервале 0,1 < M < 1, ноль в разряде целых и разделитель десятичных разрядов в представление не включаются, т. е. мантисса содержит только цифры дробной части.
Первая цифра мантиссы также не сохраняется (она для всех равна единице)
Количество разрядов числа при переходе от одной системы счисления к другой в общем случае меняется. Количество разрядов числа в системах счисления p и q будут различаться в σ раз.

Пример. Количество цифр в числе 99 и его представлении в двоичной системе счисления 99 = 1100011 ; т. е. двоичная запись требует 7 цифр вместо 2 в десятичной.
σ= ln(10)/ln(2) = 3,322
следовательно, количество цифр в десятичном представлении нужно умножить на 3,322 и округлить в большую сторону: 2*3,322 = 6,644 ≈7.

В процессе выполнения арифметических действий с нормализованными числами отдельно обрабатываются мантиссы и порядки.
Сложение нормализованных чисел
находиться модуль разности ∆k =abs(k 1- k 2)
сдвиг вправо на ∆k разрядов мантиссы того числа, у которого k меньше.
сложение мантисс, порядок результата присваивается значение большего из имеющихся
результат нормализуют.

Выполнить вычитание двоичных нормализованных чисел 0.10101 . 210 и 0.11101 . 21.
Разность порядков уменьшаемого и вычитаемого здесь равна 1, поэтому перед вычитанием мантисса второго числа сдвигается на один разряд вправо:

Выполнить умножение двоичных нормализованных чисел:
(0.11101 . 2101) . (0.1001 . 211)
(0.11101 . 0.1001) . 2(101+11) = 0.100000101 . 21000.