Внутренняя форма представления данных в компьютере и недесятичные системы счисления. Часть 2.

Дополнение к "Вводной лекции по курсу программирования для начинающих".

Часть 2.

3. Перевод из двоичной системы в десятичную и обратно.
Коль скоро мы видим, что компьютер работает в двоичной системе, в то время как в обыденной жизни мы употребляем десятичную, естественно возникает вопрос: а как перевести число из одной системы в другую? Не считать же по порядку с нуля. Конечно, для маленьких чисел можно и посчитать, а вот как быть с большими?

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

1945 = 1*1000 + 9*100 + 4*10 + 5*1 = 1*10**3 + 9*10**2 + 4*10**1 + 5*10**0

А что же будет означать двоичное число, скажем, 110101? Давайте представим его так же, как мы только что представили десятичное 1945, только учтем, что система у нас теперь двоичная:

110101 = 1*2**5 + 1*2**4 + 0*2**3 + 1*2**2 + 0*2**1 + 1*2**0 =
= 1*32 + 1*16 + 1*4 + 1*1 = 53

Все! Число переведено. 110101 в двоичной соответствует 53 в десятичной системе.

Теперь давайте переводить обратно, из десятичной в двоичную. Алгоритм перевода будет такой:
1. Делим исходное число на два, потом результат еще на два и т.д., пока частное не станет равным нулю. При делении запоминаем остатки.
2. Выписываем остатки в порядке, обратном их появлению.

53 / 2 = 26 (остаток 1)
26 / 2 = 13 (0)
13 / 2 = 6 (1)
6 / 2 = 3 (0)
3 / 2 = 1 (1)
1 /2 = 0 (1)

Если теперь выписать остатки в обратном порядке, получим 1 1 0 1 0 1, то есть как раз то число, которое мы надеялись получить!

Задание 3. Переведите из десятичной системы в двоичную чилсо 1945. Для того, чтобы убедиться, что результат получился правильный, переведите его обратно в десятичную систему. Должно снова выйти 1945.

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

А. Сложение.

Код:
11100
+
10110
--------
110010

Пояснения:
Младший разряд: 0+0=0
Второй разряд: 0+1=1
Третий разряд: 1+1=2 = 10(двоичное) = 0 и 1 перенос
Четвертый разряд: 1+0+1 переноса = 10(дв.) = 0 и 1 перенос
Пятый разряд: 1+1+1 переноса=3 = 11(дв.) = 1 и 1 переносится в шестой разряд.

Б. Вычитание.
Код:
110010
-
10110
---------
11100

Младший разряд: 0-0=0
Второй разряд: 1-1=0
Третий разряд: 0-1= Заняли в старшем разряде1, добавилось 2 в текущем разряде. 2-1=1
Четвертый разряд: 0-0-1 занятое третьим разрядом, занимаем в следующем разряде, получилось 2 в текущем разряде. 2-1=1
Пятый разряд: 1-1-1 занятое четвертым разрядом, занимаем в следующем разряде, добавилось 2 в текущем разряде. 1+2-1-1=1
Шестой разряд: Была 1, но ее заняли для пятого разряда, остался 0. Как и в десятичной системе, нули перед числом обычно не записываются.

В. Умножение.
Код:
10110
*
1011
-----------
10110
10110
00000
10110
-----------
11110010

Г. Деление.
Код:
11110010|1011
-
1011 |________
------- | 10110
10000
-
1011
-----------
1011
-
1011
-----------
00


Задание 4. Убедитесь, что все действия в вышеприведенных примерах выполнены правильно. Для этого переведите все числа в десятичную систему.

Задание 5. Проследите ход выполнения операций и выполните подобные арифметические действия над любыми числами самостоятельно.


5. Другие часто используемые недесятичные системы счисления. Восьмеричная система.
В принципе, знания двоичной системы счисления вполне достаточно для того, чтобы понять, что происходит в компьютере. Однако, вы, вероятно, уже заметили, что числа в двоичной системе получаются очень длинными. То есть, действия в ней проводить несложно, но уж очень много писанины (а где много писанины - там много и возможностей для ошибок!).

Поэтому в некоторое время возникла идея: почему бы для записи внутреннего представления чисел не использовать другую систему, более экономичную с точки зрения записи чисел? Нормальная десятичная не подходит, поскольку преобразования из двоичной в десятичную и обратно довольно трудоемки. Таким образом, требования к кандидату следующие:
1. Числа должны записываться сравнительно компактно (сравнимо с числами в десятичной системе).
2. Преобразования из этой системы в двоичную и обратно должны быть элементарными и не требовать вычислений.

Первым кандидатом на эту роль оказалась восьмеричная система, то есть система с основанием восемь. По аналогии с предыдущими рассуждениями легко понять, что это означает: восемь цифр от 0 до 7, при счете подряд после 7 прибавляется единица в старшем разряде (10), при сдвиге на один разряд влево число увеличивается в восемь раз и т.д.

Почему же восьмеричная система оказалась настолько удобна? Вы наверняка обратили внимание на то, что восемь - это степень двойки, то есть восемь - это два, возведенное в третью степень. Именно благодаря этому перевод из двоичной системы в восьмеричную и обратно очень упрощается. Давайте посмотрим, как это выглядит на примере нескольких первых чисел:
Двоичная
Система
0
1
10
11
100
101
110
111
1 000
1 001
1 010
. . .
10 110
10 111
11 000
. . .
111 111
1 000 000 Восьмеричная
Система
0
1
2
3
4
5
6
7
10
11
12
. . .
26
27
30
. . .
77
100
Десятичная
Система
0
1
2
3
4
5
6
7
8
9
10
. . .
22
23
24
. . .
63
64


Если мы внимательно присмотримся к двоичной и восьмеричной записям, мы увидим, что одной восьмеричной цифре всегда в точности соответствует комбинация из трех двоичных цифр (000 - 0, 001 - 1, 010 - 2, 011 - 3, 100 - 4, 101 - 5, 110 - 6, 111 - 7), а потому, разбив запись любого двоичного числа на тройки справа налево (их еще называли триадами), мы легко получим его восьмеричное представление. Наоборот, в восьмеричной записи любого числа, заменив каждую восьмеричную цифру на соответствующую триаду, мы получим двоичное представление этого числа. Это свойство напрямую следует из того факта, что восемь - это два в третьей степени.

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

Восьмеричное 7205 = 7*8**3 + 2*8**2 + 0*8**1 + 5*8**0 = 7*512 + 2*64 + 5 = 3717
Таким образом, 7205 восьмеричное это 3717 десятичное.

Теперь давайте сделаем обратный перевод:
3717 / 8 = 464 (остаток 5)
464 / 8 = 58 ( 0 )
58 / 8 = 7 ( 2 )
7 / 8 = 0 ( 7 )

Выписывая остатки в обратном порядке (сравните с двоичной системой), получим 7 2 0 5, что и требовалось!

Автор: Sashok Sam