6. Раздел 3

7. Арифметические основы информатики Лекция 4. Системы счисления

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

- возможность представления любого числа в рассматриваемом, заранее назначенном диапазоне величин;

- единственность представления (любая комбинация символов соответствует одному и только одному числу);

- простоту операций с числами.

Все системы счисления разделяются на два больших класса – непозиционные и позиционные.

В непозиционнойсистеме счисления значения символов не зависят от положения в числе. Для образования таких систем используют, в основном, операции сложения и вычитания. Например, система с одним символом-палочкой встречалась у многих народов. Для изображения числа в этой системе нужно записать определенное множество палочек, равное данному числу. Эта система не эффективна, т.к. запись числа получается длинной. Другим примером непозиционной системы счисления является римская система, использующая набор следующих символов: I, V, X, L, C, D и т.д. В этой системе имеются отклонения от правила независимости значения цифры от положения в числе. В числах IV и VI символ I принимает соответственно значения –1 и +1.

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

903,87=9´10²+0´10¹+3´10⁰+8´10^-1+7´10^-2.

Десятичная система счисления наиболее распространена в вычислительной практике. Однако своему распространению она обязана не каким-то особым преимуществом перед другими системами, а достаточно случайному обстоятельству – наличию у человека десяти пальцев на руках.

Количество различных цифр, применяемых в позиционной системе счисления, называется ее основанием(для десятичной системы - от 0 до 9- десять ).

В позиционной системе с некоторым основанием р используются р различных между собой цифр от 0 до р -1. Так последовательность цифр

A_(p)= a_n-1 a_n-2… a₁ a₀, a_-1… a_-m

в р-ичной системе означает число

где a_i - цифры системы счисления, n и m – число целых и дробных разрядов числа.

Обычно в качестве двух младших цифр во всех системах счисления используются знаки 0 и 1. При этом основание системы счисления р записывается в виде последовательности цифр 10 (это не десять, а один ноль!). В скобках указывают систему счисления, в которой записывается число, т.е 10_(р).

В вычислительной технике широко используются двоичная, восьмеричная и шестнадцатеричная системы счисления. При этом для представления чисел в двоичной системе используются две цифры 0 и 1, в восьмеричной – 0, 1,…,7 и в шестнадцатеричной – цифры 0, 1,…,9 и знаки A, B, C, D, E, F (часто вместо этих знаков записывают символы

).

Пример 3.1. В качестве примера возьмем двоичное число 1001,1101₍₂₎. В соответствии с равенством (3.1 ) двоичное число можно определить следующим образом:

1001,1101₍₂₎=1´2³+0´2²+0´2¹+1´2⁰+1´2^-1+1´2^-2 + 0´2^-3 + 1´2^-4.

Если по правилам десятичной арифметики выполнить действия в правой части приведенного равенства, то можно получить значение этого числа в десятичной системе счисления (десятичный эквивалент двоичного числа):

1001, 1001₍₂₎=9,8125₍₁₀₎.

В табл. 3.1 приведены эквиваленты десятичных чисел в двоичной, восьмеричной и шестнадцатеричной системах счисления.

Таблица 3.1

Десятичная	Эквиваленты в системах счисления			Десятичная	Эквиваленты в системах счисления
цифра	p=2	p=8	p=16	цифра	p=2	p=8	p=16
0	0	0	0	8	1000	10	8
1	1	1	1	9	1001	11	9
2	10	2	2	10	1010	12	A
3	11	3	3	11	1011	13	B
4	100	4	4	12	1100	14	C
5	101	5	5	13	1101	15	D
6	110	6	6	14	1110	16	E
7	111	7	7	15	1111	17	F

Для записи одного и того же значения в различных системах счисления требуется разное число позиций или разрядов. Например, 96₍₁₀₎=140₍₈₎=1100000₍₂₎. Чем меньше основание системы счисления, тем больше длина числа (длина разрядной сетки). Если длина разрядной сетки задана, то это ограничивает максимальное по абсолютному значению число, которое можно записать.

Пусть длина разрядной сетки равна числу N. Тогда

A _{(p )max} = p^N - 1.

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

N=log_P (A_(P)max+1).

Интервал числовой оси, заключенный между максимальным и минимальными числами, называется диапазоном представления(ДП) чисел в данной системе счисления для заданной длины разрядной сетки:

-A _(P)max ДП A_(P)max .

В ЭВМ длина обрабатываемых чисел обычно ограничена следующими значениями: 1 байт (8 двоичных разрядов), 2 байта (16 разрядов), 4 байта (32 разряда) и 8 байт (64 разряда). Соответственно ограничены и значения чисел, записываемых с использованием этих разрядных сеток. Так, максимальное целое положительное число, которое можно записать с использованием 16 двоичных разрядов, равно 2¹⁶-1 = =65535.

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

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

Рассмотрим сложение.

Сложение производится поразрядно, начиная с младшего, используя соответствие таблицы сложения. Так, для двоичной, системы счисления имеем:

0+0 = 0

0+1 = 1

1+0 = 1

1+1 =10.

Примеры сложения чисел.

Пример 3.2. Пример 3.3.

101011, 1101₍₂₎245,0₍₈₎

10010, 1011₍₂₎734,7₍₈₎

111110, 1000 ₍₂₎. 1201,7₍₈₎.

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

a_k = a_i - a_jпри a_i a_j,

a_k = p + a_i– a_jпри a_i< a_j,

т.е. при a_i< a_jзанимается ”1“ старшего разряда, содержащая р единиц младшего разряда. Таблица вычитания для двоичной системы счисления:

0-0=0

1-0=1

1-1=0

10-1=1 .

Примеры вычитания чисел:

Пример 3.4. Пример 3.5.

1001,01₍₂₎ 1352,2₍₈₎

110,11 ₍₂₎743,5 ₍₈₎

0010,10 ₍₂₎. 406,5₍₈₎ .

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

.

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

0´0=0

0´1=0

1´0=0

1´1=1.

Пример 3.6:

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

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

Пример 3.7. Разделить число 111111,01₍₂₎на 101,1₍₂₎.

Умножим оба числа на 100 ₍₂₎и будем делить два целых числа:

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

Использование в ЭВМ двоичной системы счисления связано с преодолением дополнительных трудностей, вызванных необходимостью перевода вводимых в ЭВМ чисел в двоичную систему счисления и обратного перевода числовых данных при выводе информации из ЭВМ. Эти преобразования информации в ЭВМ осуществляются автоматически с использованием специально разработанных методов.

Пусть задано число А_(q)в q–ичной системе счисления. Требуется найти запись этого числа в р-ичной системе счисления, т.е. В_(р).

Метод непосредственного замещения

Перевод чисел этим методом выполняется следующим образом:

- заданное число А_(q)представляется в виде (3.1):

A_(q)=a_n-1´q^n-1+…+a₀´q⁰+a _–1´q^-1+…+a_-m´q^-m ;

- все цифры a_iи основание q в правой части записываются (замещаются) в системе счисления с новым основанием p и выполняются необходимые операции. При этом, если р>q, то изображение цифр в p-ичной системе совпадает с изображением чисел в q-ичной системе. Если же p<q, то необходимо знать представление чисел от p до q в системе счисления с основанием р.

Пример 3.8. Перевести число 357 ₍₈₎в десятичную систему счисления.

Решение. 357₍₈₎=3´8²+5´8¹+7´8⁰=192+40+7=239₍₁₀₎.

Пример 3.9. Перевести число 13,5₍₁₀₎в двоичную систему счисления.

Решение. 13,5₍₁₀₎=1´10¹+3´10⁰+5´10^-1=1´1010+11+101/1010=1101,1₍₂₎.

Метод последовательного деления на основание

Этот метод используется для перевода только целых чисел.

Пусть число A_(q)требуется записать в р-ичной системе. Допустим, что такое представление получено и новое число В_(р)имеет вид:

A_(q) = B_(p) = b_n-1 b_n-2 … b₁ b_{0 (p)} = b_n-1´p^n-1 + b_n-2´p^n-2 + … + b₁ p¹+ b₀.

Разделим число A_(q)на р. Так как b₀<p, то в результате деления получим целую часть:

A₁ = b_n-1´p^n-2 + b_n-2´p^n-3 + … + b₁

и остаток b₀. Отсюда следует, что остаток от деления заданного числа на основаниe р равен значению цифры младшего разряда р-ичного числа. При этом, если p<q, то остаток является цифрой р-ичной системы счисления, а при p>q остаток представляет собой число в q-ичной системе счисления, которое соответствует цифре р-ичной системы (заметим, что деление должно выполняться в q-ичной системе счисления, т.е. в системе, в которой задано исходное число).

Чтобы найти цифру b₁следует отбросить остаток b₀, a А₁вновь разделить на р. Получим целую часть

А₂= b_n-1´p^n-3+ … b₃´p + b₂

и остаток b₁, который равен значению цифры очередного разряда. Последовательное деление продолжается до тех пор, пока не получится частное, меньшее р. Это частное является цифрой старшего разряда искомого р-ичного числа.

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

Пример 3.10. Перевести десятичное число 38 в двоичную систему счисления.

Решение:

Ответ: B₍₂₎=b₅ b₄ b₃ b₂ b₁ b₀₍₂₎=100110₍₂₎.

Пример 3.11. Провести обратный перевод числа B₍₂₎=100110₍₂₎в десятичную систему счисления.

Решение: Сначала новое основание системы счисления представим в двоичной системе: 10₍₁₀₎=1010₍₂₎. Далее делим число 100110₍₂₎на основание 1010₍₂₎.

100110

1010

10010

1010

Ответ: 100110₍₂₎=b₁b_{0 (10)}= 38₍₁₀₎.

Метод последовательного умножения на основание

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

Пусть правильную дробь A_(q)требуется записать в системе счисления с основанием р. Предположим опять, что эта запись найдена

A_(q)=B_(p)=0, b_-1 b_-2… b_-m(p)=b_-1´p^-1+b_-2´p^-2+…+b_-m ´p^-m.

Если умножить число А на основание новой системы счисления p, то целая часть произведения будет равна b_-1, а дробная

A₁=b_-2´p^-1+b_-3´p^-2 + … + b_-m´p^-m+1,

причем A₁-правильная дробь, т.к. все a_i < p.

Таким образом, в результате умножения числа А на основание р получается целая часть, равная значению цифры старшего разряда р-ичного числа. Продолжая умножать дробные части A_jна основание р (целые части при умножении отбрасываются), можно получить остальные цифры искомой дроби: ими являются целые части получаемых произведений. При этом, если p<q, то целые части произведения являются цифрами р-ичной системы счисления, а при p>q целые части представляют собой числа в q-ичной системе счисления, которые необходимо заменить цифрами р-ичной системы.

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

Пример 3.12. Перевести десятичную дробь A₍₁₀₎=0,6875₍₁₀₎в двоичную систему счисления.

Решение. Выполним следующие действия:

Ответ: B₍₂₎=0, b_-1b_-2b_-3b_-4=0,1011₍₂₎.

Пример 3.13. Провести обратный перевод двоичного числа 0,1011₍₂₎в десятичную дробь.

Решение. В данном примере p>q, поэтому сначала переведем р₍₁₀₎в двоичную систему счисления: р=10₍₁₀₎=1010₍₂₎. Выполним последовательные умножения:

Ответ: B₍₁₀₎=0, b_-1b_-2b_-3b_-4= 0,6875.

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

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