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

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

План лекции.

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

2. Перевод целых и дробных чисел из одной системы счисления в другую.

3. Арифметические операции в двоичной системе счисления и представление

чисел в других системах счисления.

Вопрос 1.

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

два отличия: 1) числа записываются в двоичной системе счисления; 2) для

записи и обработки чисел отводится конечное количество разрядов.

Способ представления чисел определяется системой счисления.

ОПР1. Система счисления - это правило записи чисел с помощью заданного

набора специальных знаков - цифр.

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

объединить в несколько групп: унарная, непозиционные и позиционные.

1 группа. Унарная - это система счисления, в которой для записи чисел

используется только один знак - I («палочка»). Следующее число получается

из предыдущего добавлением новой I единицы, их количество равно самому

числу.

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

Z[1].

2 группа. Из непозиционных наиболее распространенной можно считать Римскую

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

латинскими буквами: 1 - I, 5 - V, 10 - X, 50 - L, 100 - C, 500 - D, 1000 -

M. Все другие числа строятся комбинаций базовых в соответствии со

следующими правилами:

1. Если цифра меньшего значения стоит справа от большей цифры, то их

значения суммируются, если слева - то меньшее значение вычитается из

большего.

2. Цифры I, X, C, M могут следовать подряд не более трех раз каждая.

3. Цифры V, L, D могут использоваться в записи числа не более одного

раза.

Например: XIX - 19, MDXLIX - 1549.

Запись чисел в такой системе громоздка и неудобна, но еще более неудобным

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

3 группа. В настоящее время для представления чисел применяются

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

ОПР2. Позиционными называются системы счисления, в которых значение каждой

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

других цифр.

Наиболее распространенной и привычной является система счисления, в

которой для записи чисел используется 10 цифр. Число представляет собой

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

числа - основания системы счисления.

Например: 272, 12 = 2 * 10^2 + 7 * 10^1 + 2 * 10^0 + 1 * 10^-1 + 2 *

10^-2.

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

счисления - пятиричной, шестиричной, двенадцатиричной и т.п.

Общим для унарной и римской систем счисления является то, что значение

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

базисных цифр, из которых составлено число, независимо от их позиции в

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

В отличие от них позиционное представление считается

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

операциями умножения и сложения.

По принципу, положенному в основу десятичной системы счисления можно

построить системы с иным основанием. Пусть p - основание системы

счисления, k - общее число цифр числа, тогда любое число Z может быть

представлено в виде многочлена со степенями р: Z[p] = a[k-1] * p^k-1 +

a[k-2] * p^k-2 + … + a[1] * p^1 + a[0] * p^0. (*)

Первое допустимое значение р = 2 - оно является минимальным для

позиционных систем. Система счисления с основанием 2 называется двоичной.

Цифрами двоичной системы являются 0 и 1, а форма представления числа

строится по степеням 2.

Вопрос 2.

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

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

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

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

операций по правилам арифметики недесятичных систем счисления. По этой

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

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

арифметические операции выполнить достаточно легко.

Алгоритмы работы с целыми числами.

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

10 в другую систему.

1. целочисленно разделить исходное число Z(10) на основание новой системы

счисления (p) и найти остаток от деления - это будет цифра 0-го

разряда числа Z(p).

2. частное от деления снова целочисленно разделить на (р) с выделением

остатка, процедуру продолжать до тех пор, пока частное от деления не

окажется меньше (р).

3. образованные остатки от деления, поставленные в порядке, обратном их

получения, и представляют Z(p).

Примеры: 123(10) перевести в (5), во (2) и т.п.

Способ 2. Алгоритм перевода Z(p) в Z(10).

Для этого преобразования используют формулу (*).

Примеры: 443(5) перевести в (10), 1110(2) перевести (10) и т.п.

Алгоритмы работы с дробными числами.

Вещественное число, в общем случае содержит целую и дробную часть, всегда

можно представить в виде суммы целого числа и правильной дроби. Рассмотрим

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

правильную дробь в исходной системе счисления (р) будем записывать в виде

0,Y(p). Последовательность рассуждений весьма напоминает проведенную ранее

для целых чисел.

Способ 3. Алгоритм перевода из (10) в другую систему (р).

1. умножить исходную дробь в 10-ной системе счисления на основание (р),

выделить целую часть - она будет первой цифрой новой дроби, отбросить

целую часть;

2. для оставшейся дробной части операцию умножения с выделением целой и

дробной части повторить, пока в дробной части не окажется 0 или не

будет достигнута желаемая точность конечного числа.

3. записать дробь в виде последовательности цифр после ноля с

разделителем в порядке их появления.

Примеры: выполнить преобразование 0,375 (10) перевести (2) и т.п.

Способ 4. Перевод 0,Y(p) в 0,Y(10) сводится к вычислению значения формы

(*) в десятичной системе счисления.

Примеры: 0,011(2) перевести в (10) и т.п.

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

конечной в исходной системе счисления, дробь может оказаться бесконечной в

новой системе. Соответственно, рациональное число в исходной системе может

после перехода превратиться в иррациональное. Справедливо и обратное.

Вопрос 3.

Рассмотрим, как с беззнаковыми числами выполняются арифметические

операции, не меняющие типа числа.

Сложение производится согласно таблице сложения, которая для двоичных

чисел имеет вид:

0 + 0 = 0 0 + 1 = 1

1 + 0 = 1 1 + 1 = 10

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

а 1 переносится в старший разряд.

Примеры: 0101 + 1100 и т.п.

0101

+ 1100

10001

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

чисел имеет вид:

0 * 0 = 0 0 * 1 = 0

1 * 0 = 0 1 * 1 = 1

Примеры: 1101 * 101 и т.п.

1101

* 101

1101

+ 0000

1101

1000001

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

один двоичный разряд влево и повторения первого сомножителя в тех

разрядах, где второй сомножитель содержит 1, и сдвига без повторения в

разрядах с 0.

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

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

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

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

регистров и устройств используются системы счисления с основанием 8 и 16.

Представление чисел в системах счисления

+------------------------------------------------------------------------+

| 10-ная | 2-ная | 8-ная | 16-ная |

|-----------------+-----------------+-----------------+------------------|

| 0 | 0 | 0 | 0 |

|-----------------+-----------------+-----------------+------------------|

| 1 | 1 | 1 | 1 |

|-----------------+-----------------+-----------------+------------------|

| 2 | 10 | 2 | 2 |

|-----------------+-----------------+-----------------+------------------|

| 3 | 11 | 3 | 3 |

|-----------------+-----------------+-----------------+------------------|

| 4 | 100 | 4 | 4 |

|-----------------+-----------------+-----------------+------------------|

| 5 | 101 | 5 | 5 |

|-----------------+-----------------+-----------------+------------------|

| 6 | 110 | 6 | 6 |

|-----------------+-----------------+-----------------+------------------|

| 7 | 111 | 7 | 7 |

|-----------------+-----------------+-----------------+------------------|

| 8 | 1000 | 10 | 8 |

|-----------------+-----------------+-----------------+------------------|

| 9 | 1001 | 11 | 9 |

|-----------------+-----------------+-----------------+------------------|

| 10 | 1010 | 12 | A |

|-----------------+-----------------+-----------------+------------------|

| 11 | 1011 | 13 | B |

|-----------------+-----------------+-----------------+------------------|

| 12 | 1100 | 14 | C |

|-----------------+-----------------+-----------------+------------------|

| 13 | 1101 | 15 | D |

|-----------------+-----------------+-----------------+------------------|

| 14 | 1110 | 16 | E |

|-----------------+-----------------+-----------------+------------------|

| 15 | 1111 | 17 | F |

+------------------------------------------------------------------------+