Системы счисления лекции
Системы счисления лекции
Тема: Представление и обработка чисел в компьютере.
План лекции.
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 |
+------------------------------------------------------------------------+
|