Библиотека сайта rus-linux.net
| Назад | Введение в мир программирования Глава 2. Архитектура компьютера |
Вперед |
Ячейки памяти и позиционные системы счисления
Память компьютера представляет из себя последовательность ячеек памяти фиксированного размера.
Ячейка памяти - это минимальная единица памяти, к которой можно обращаться из программы.
Размер одной ячейки памяти зависит от модели компьютера (например, DEC PDP-15
работал с ячейками памяти, содержавшими по 18 бит в каждой). В персональных ЭВМ обычно
используются ячейки памяти, состоящие из 8 бит. Такие ячейки могут быть
названы 8-разрядными, то есть содержащими по восемь двоичных разрядов
(понятие ``разряд числа'' применяется в позиционных системах счисления и обозначает
структурный элемент представления числа). Ячейка данного размера может
содержать, например, значение 01010010.
С помощью 8-разрядного двоичного числа можно представлять десятичные числа
от 0 до 255. Например, если взять двоичное число 01111101 и перевести
его в десятичное, то получится: 20 + 01 + 22
+ 23 + 24 + 25 + 26 + 07 = 125.
Если же нужно перевести десятичное число в двоичное, то это тоже не составит проблем.
Всё дело в том, что и двоичная и десятичная и шестнадцатиричная системы счисления (наиболее
часто используемые в программах на ассемблере) являются позиционными (значение каждого
знака в числе, записанном в такой системе, зависит от того какому
разряду [месту] он соответствует). Умение быстро осуществлять перевод
чисел из одной позиционной системы счисления в другую является одной из существенных
характеристик хорошего программиста. Поэтому остановимся на этом вопросе подробнее.
Устный перевод числа из одной позиционной системы счисления в другую
В средней школе (как в российской, так и в советской) обучение методам перевода чисел из одной системы счисления в другую занимает значительное количество часов. Однако, к сожалению, обычно детей учат медленным методам (деление уголком и т. п.), а ещё хуже - предлагают использовать таблицы соответствий, часто не объясняя логику составления таких таблиц.
Итак, мы предлагаем читателю, испытавшему на себе недостатки школьного образования, освоить быстрый метод перевода чисел из одной позиционной системы счисления в другую.
Переход от десятичной системы к двоичной и наоборот
Во-первых, нужно запомнить что любое десятичное число
можно разбить на сумму слагаемых, каждое из которых можно
выразить степенью числа два. Например:
23 = 16 + 4 + 2 + 1 = 24 + 22 + 21 + 20.
Во-вторых, нужно знать наизусть (или хотя бы иметь при себе) таблицу степеней числа два. Как минимум, вы должны помнить, что:
20 | = | 1 |
21 | = | 2 |
22 | = | 4 |
23 | = | 8 |
24 | = | 16 |
25 | = | 32 |
26 | = | 64 |
27 | = | 128 |
28 | = | 256 |
29 | = | 512 |
210 | = | 1024 |
211 | = | 2048 |
212 | = | 4096 |
В-третьих, любое, даже самое большое, десятичное число может быть представлено как сумма
степеней числа два единственным образом! Например, если взять относительно большое
число 395, то его можно разложить следующим образом: 39510 = 256 + 128 + 8 + 2 + 1 =
28 + 27 + 23 + 21 + 20 = 1100010112.
И никак иначе!
Таким образом, для быстрого перевода десятичного числа в двоичное нужно вспомнить
значение степени числа два, представляющее из себя маскимально большое слагаемое переводимого числа
(это и будет первое слагаемое). Например, если взять десятичное число 1079, то
мы можем смело брать в качестве первого слагаемого 210, то есть 1024.
Далее нужно вычесть 1024 из 1079: 1079 - 1024 = 55. Потом -
найти максимально большое число, меньшее, чем 55 и являющееся степенью числа 2.
Это будет 32, то есть 25. Продолжать нужно до тех пор пока не будут найдены все
слагаемые, на которые можно разложить десятичное число для того, чтобы быстро перевести
его в двоичный формат записи.
У нас получилось: 1079 = 1024 + 32 + 16 + 4 + 2 + 1. Помните, что мы уже раскладывали
23 на слагаемые, которые удобно переводить в двоичное представление? В этом примере мы имеем
абсолютно такие же результаты!
Любопытный читатель может спросить: какие слагаемые удобно переводить в двоичное представление?.
Конечно же те, которые являются степенями числа два. Почему? Вспомните, что двоичная система является
позиционной. Это значит, что значение степени слагаемого позволяет определить его место
(разряд) в двоичном числе (если слагаемое больше нуля, то соответствующий разряд
двоичного числа будет равен единице). Например, 1079 = 1024 + 32 + 16 + 4 + 2 + 1
= 210 + 25 + 24 + 22 + 21 + 20 =
100001101112. Мы получили 11-ти разрядное двоичное число, разряды которого
установлены в единичное значение в том случае, если их порядковый номер (начиная с правого края)
совпадает со значением степени слагаемого суммы, на которую (единственным образом!)
можно разложить число 1079.
Попрактиковав предлагаемый метод (очень похожий на "метод разностей")
некоторое время, вы научитесь устно и очень быстро переводить
даже большие числа из десятичной системы счисления в двоичную и наоборот (к примеру, 1001010112 =
28 + 25 + 23 + 21 + 20 = 256 + 32 + 8 + 2 + 1 = 29910
).
Другие варианты перехода между системами счисления
Овладев предложенным нами методом перевода чисел из десятичной системы в двоичную, легко научиться работать и с другими позиционными системами счисления. Более того, мы утверждаем что начинать лучше всего именно с этого метода (он наглядный и лежит в основе всех остальных: десятичную систему счисления удобно использовать как промежуточную, к примеру, если надо перевести число из 5-ной в 3-ную систему).
Вот как это может выглядеть:
4435 = 4*52 + 4*51 + 3*50 = 12310
= 26 + 25 + 24 + 23 + 21 + 20
= 11110112.
В свою очередь, для работы с шестнадцатиричной системой счисления удобнее всего
использовать двоичную в качестве основы (любое 16-ое число может быть получено
последовательным преобразованием четытрёхразрядных групп двоичного числа). Например,
в 100101002 имеется восемь двоичных разрядов. Начиная с правого края будет
переводить четёрыхразрядные группы двоичных разрядов сначала в десятичные числа,
а потом в шестнадцатиричные разряды. Таким образом: 100101002 = 9416.
Или, например, 10111101012 = 2F516 = 0010111101012
(обратите внимание, что в этом двоичном числе десять разрядов:
те разряды, которые необходимы для формирования трёх групп по четыре разряда
в каждой, мы заполняем нулями).
Автоматизированный перевод числа из одной позиционной системы счисления в другую
Основываясь на принципе единственности разложения числа на сумму чисел, являющихся степенями целевой системы счисления (об этом принципе говорилось выше), мы можем автоматизировать процесс перевода числа из одной позиционной системы счисления в другую, написав специальную программу. Давайте проанализируем то, как она работает.
program numbers;
const n = 10;
var x,y,z,opnum,tmp10: word;
i,j,l:word;
newbase:word;
k:string[10];
base:string[10];
left:array[1..10] of word;
exc1,exc2,exc3:word;
begin
writeln;
write('The base of the positional numeral system: ');
readln(base);
val(base,y,exc1);
if((y>10) or (y<2)) then
begin
writeln('Base of the numeral system should not be greater than 10 or lesser than 2!');
end
else if(exc1 <> 0) then
begin
writeln('Input should contain only positive integers!');
end
else
begin
write('Provide a number to be analysed: ');
readln(k);
val(k, x, exc2);
if(exc2 <> 0) then
begin
writeln('Input should contain only positive integers!');
end
else
begin
writeln('-----------');
if (y=10) then
begin
for newbase:=2 to 9 do
begin
writeln;
write('In ',newbase,' numeral system x = ');
i:=1; opnum:=x;
while (opnum div newbase) > 0 do
begin
left[i]:=opnum mod newbase; opnum:=opnum div newbase; i:=i+1;
end;
left[i]:=opnum mod newbase;
for j:=i downto 1 do write(left[j]);
end;
writeln;
end
else
begin
j:=0; i:=1;
for l:=length(k) downto 1 do
begin
val(k[i], z, exc3);
j:=j+z*(y pow (l-1));
i:=i+1;
end;
tmp10:=j;
writeln('In 10 numbering system x = ',j,'.');
for newbase:=2 to 9 do
begin
writeln;
write('In ',newbase,' numbering system x = ');
i:=1;
opnum:=tmp10;
while (opnum div newbase) > 0 do
begin
left[i]:=opnum mod newbase; opnum:=opnum div newbase; i:=i+1;
end;
left[i]:=opnum mod newbase;
for j:=i downto 1 do write(left[j]);
end;
writeln;
end;
writeln;
writeln('-----------');
writeln;
end;
end;
end.
Во-первых, видно, что это никакой не ассемблер (пока что!), а самый настоящий Pascal (программа
может быть скомпилирована с помощью GNU Pascal, см.:
http://www.gnu-pascal.de/gpc/h-index.html). Она может работать
с 2-ной, 3-ной, 4-ной, 5-ной, 6-ной, 7-ной, 8-ной, 9-ной, 10-ной системами счисления.
Сначала пользователю предлагается ввести основание системы счисления, из
которой число (задаваемое позже) будет переводиться во все остальные системы счисления.
Чтение ввода осуществляется с помощью функции readln.
Далее функция val проверяет, является ли вводимое значение целым
положительным числом. Если не является, то выдаётся соответствующее сообщение об
ошибке и программа завершает работу.
Если указанное пользователем основание системы счисления является
допустимым, то программа запрашивает ввод числа, которое необходимо
проанализировать (перевести в другие системы счисления). Этот запрос
снова выполняется функцией readln, которая принимает ввода
пользователя и записывает его в переменную k: readln(k).
А вот теперь начинается самое интересное. Если основание системы счисления, в которой представлено анализируемое число равно 10, то выполняется блок кода, осуществляющий перевод этого числа во все остальные системы счисления, поддерживаемые программой (2-ную, 3-ную, 4-ную, 5-ную, 6-ную, 8-ную, 9-ную).
Давайте разберём этот блок кода построчно.
for newbase:=2 to 9 do
begin
writeln;
write('In ',newbase,' numeral system x = ');
i:=1; opnum:=x;
while (opnum div newbase) > 0 do
begin
left[i]:=opnum mod newbase; opnum:=opnum div newbase; i:=i+1;
end;
left[i]:= opnum mod newbase;
for j:=i downto 1 do write(left[j]);
end;
Переменная newbase содержит основание целевой системы счисления
(той, в которую мы переводим число, заданное в ответ на запрос программы "Provide a number to be analysed"
- "Укажите число для анализа"). Цикл for newbase:=2 to 9 do begin ... end; позволяет
последовательно провести перевод значения переменной x сначала в двоичную, потом в троичную
и так далее вплоть до 9-ричной системы счисления.
Напомним, что значение x мы задали в ответ на запрос "Provide a number to be analysed".
Цикл while (opnum div newbase) > 0 do begin ... end; использует две дополнительные
переменные: opnum и i. Видно, что i является индексом для обращения
к содержимому массива left[] и инкрементируется (то есть увеличивается на единицу) при
каждом очередном шаге цикла while.
Не забывайте, что в языке Паскаль, в отличие, например,
от языка Си, индексы массива могут иметь значения начиная с единицы,
а не с нуля. Именно поэтому запись начального значения переменной i
осуществляется следующим образом: i:=1.
Но зачем нам нужен массив left[]? И почему он называется именно так, а не иначе?
Этот массив применяется для промежуточного хранения разрядов числа в целевой системе счисления
(newbase). Каждый очередной разряд данного числа, добавляемый в массив left[],
оказывается левее предыдущего (в позиционной системе счисления каждый разряд имеет свой вес).
Давайте теперь обратим внимание на выражение opnum div newbase.
Его результат должен быть больше нуля, иначе цикл while (opnum div newbase) > 0 do begin ... end;
перестанет выполнятся и содержимое массива left[] примет законченный вид.
Как видно, оператор div принимает два операнда: opnum
(анализируемое число) и newbase (целевая система счисления).
Предложение языка Паскаль opnum div newbase преобразуется компилятором
GNU Pascal (или любым другим) и становится частью исполняемого объектного файла
a.out (имя по-умолчанию), который пригоден для загрузки в память компьютера и
непосредственного выполнения центральным процессорным устройством. Результатом выполнения предложения
opnum div newbase является целая часть от деления значения переменной
opnum на значение переменной newbase (к примеру, если 11 разделить
на 4, то целой частью от деления будет число 2).
Перейдём к предложению opnum mod newbase. Для чего оно? Оператор mod
применяется с целью нахождения остатка от деления двух чисел (например 25 mod 7 = 4). Но
зачем это нужно? Затем, что он (остаток) всегда будет меньше основания целевой системы
счисления, а следовательно, исходя из логики всей программы, будет записан
в массив left[], являясь значением одного из разрядов числа в целевой
системе счисления. Иными словами: left[i]:=opnum mod newbase.
Теперь становится понятным, что предлагаемая программа на языке Паскаль автоматизирует использование метода деления "уголком" (поэтапного деления на основание системы счисления): анализируемое число делится на основание целевой системы счисления до тех пор, пока остаток от деления не будет меньше единицы.
Неудобный для применения человеком (слишком медленный) метод деления "уголком" находит вторую жизнь, добравшись до вычислительных мощностей современных электронных устройств. Всё дело в том, что пользователю гораздо проще запрограммировать процесс деления "уголком", чем быстрый (в исполнении человека) метод, применяющий "принцип единичности разложения на слагаемые", о котором говорилось выше. Когда программа, работающая "уголком" готова, то компьютер может её выполнить почти моментально.
Предложение for j:=i downto 1 do write(left[j]); выводит на печать (то есть
на стандартное устройство вывода) содержимое массива left[].
Сессия работы с программой, разобранной выше, может быть следующей.
user@comp:~/study$ ./a.out The base of the positional numeral system: 10 Provide a number to be analysed: 849 ----------- In 2 numeral system x = 1101010001 In 3 numeral system x = 1011110 In 4 numeral system x = 31101 In 5 numeral system x = 11344 In 6 numeral system x = 3533 In 7 numeral system x = 2322 In 8 numeral system x = 1521 In 9 numeral system x = 1143 -----------
Есть ли у рассмотренной программы недостатки? Разумеется! В текущей редакции она не способна работать с большими числами. Впрочем, учебный пример и не должен быть слишком "идеальным", иначе будет скучно. Исправить указанный недостаток очень легко (достаточно внести изменения в исходный код: увеличить размер одного из используемых массивов). Читатель может сделать это самостоятельно и тогда программа начнёт работать и с теми числами, действия с которыми человеку затруднительно проводить устно (да и с карандашом в руке - тоже). Например:
user@comp:~/study$ ./a.out The base of the positional numeral system: 10 Provide a number to be analysed: 34513567876890 ----------- In 2 numeral system x = 11001101101101111000011001110011 In 3 numeral system x = 22220112100002110011 In 4 numeral system x = 3031231320121303 In 5 numeral system x = 24032021404122 In 6 numeral system x = 1330250315351 In 7 numeral system x = 151346022454 In 8 numeral system x = 31555703163 In 9 numeral system x = 8815302404 -----------
Кажется всё.
Но мы ведь совсем забыли разобраться с логикой работы программы в случае, если пользователь решил анализировать число, записанное в системе счисления, отличающейся от десятичной! Для такого положения вещей применяется блок кода, цитируемый ниже.
j:=0; i:=1;
for l:=length(k) downto 1 do
begin
val(k[i], z, exc3);
j:=j+z*(y pow (l-1));
i:=i+1;
end;
tmp10:=j;
writeln('In 10 numbering system x = ',j,'.');
Стандартная функция length(k) возвращает длину строки (количество разрядов в анализируемом числе),
которая содержит анализируемое число. Цикл for l:=length(k) downto 1 do begin ... end;
выполняется до тех пор, пока переменная l не станет равной единице.
Внутри цикла выполняется блок кода, ключевой строкой которого является
j:=j+z*(y pow (l-1));. В ней производится возведение исходного основания системы
счисления, хранящегося в переменной y в степень, которая на единицу меньше
количества разрядов в анализируемом числе (это нужно, чтобы было возможным работать
с разрядом, значение которого равно основанию исходной системы счисления в нулевой степени).
Ключевая строка, представленная выше, позволяет программно переводить
число из исходной системы счисления в десятичную, то есть делать то же самое,
что мы делали с числом 4435: 4435 = 4*52 + 4*51 + 3*50
.
Вот теперь действительно всё. Надеемся, нам удалось показать читателю то, каким образом можно обрабатывать числа, хранящиеся в ячейках памяти.
| Предыдущий раздел: | Оглавление | Следующий раздел: |
| Центральное процессорное устройство | Запоминающие устройства |