Учебное пособие по информатике 2014. Основы информатики
 Скачать 4.61 Mb.
|
|
Перевод чисел из одной системы счисления в другую При решении задач с помощью ЭВМ исходные данные обычно задаются в десятичной системе счисления; в этой же системе, как правило, нужно получить и окончательные результаты. Так как в современных ЭВМ данные кодируются в основном в двоичных кодах, то, в частности, возникает необходимость перевода чисел из десятичной в двоичную систему счисления и наоборот. При рассмотрении правил перевода чисел из одной системы счисления в другую ограничимся только такими системами счисления, у которых базисными числами являются последовательные целые числа от 0 до Р-1 включительно, где Р - основание системы счисления. Задача перевода заключается в следующем. Пусть известна запись числа х в системе счисления с каким-либо основанием Р: p n p n-1 …p 1 p 0 p -1 p -2 …, 100 где р i - цифры Р-ичной системы (0 р i Р-1). Требуется найти запись этого же числа х в системе счисления с другим основанием Q: q s q s-1 …q 1 q 0 q -1 q -2 …, где q i - искомые цифры Q-ичной системы (0 q i Q-1). При этом можно ограничиться случаем положительных чисел, так как перевод любого числа сводится к переводу его модуля и приписыванию числу нужного знака. При рассмотрении правил перевода нужно учитывать, средствами какой арифметики должен быть осуществлен перевод, т.е. в какой системе счисления должны быть выполнены все необходимые для перевода действия. Условимся считать, что перевод должен осуществляться средствами Р-ичной арифметики. Перевод Q P. Задача перевода произвольного числа х, заданного в системе счисления с основанием Q, в систему счисления с основанием Р сводится к вычислению полинома вида X=q n Q n + q n-1 Q n-1 +…+ q 1 Q 1 + q 0 Q 0 + q -1 Q -1 +…+ q -m Q -m (3.15) Для получения Р-ичного изображения выражения (3.15) необходимо все цифры q i и число Q заменить Р-ичными изображениями и выполнить арифметические операции в Р-ичной системе счисления. Заметим, что при переводе следует придерживаться правила сохранения точности изображения числа в разных системах, причем под точностью понимается значение единицы самого младшего (правого) разряда, используемого в записи числа в той или иной системе счисления. Перевод Р Q. Так как для перевода любого числа достаточно уметь переводить его целую и дробную части, рассмотрим отдельно эти два случая. 1. Перевод целых чисел. Пусть известна запись целого числа N в системе счисления с основанием Р и требуется перевести это число в систему счисления с основанием Q. Так как N - целое, то его запись в Q-ичной системе счисления имеет вид N = q s q s-1 …q 1 q 0 , где q i - искомые цифры Q-ичной системы (0 q i < Q-1). Для определения q 0 разделим обе части равенства: N = q s Q s + q s-1 Q s-1 +…+ q 1 Q 1 +q 0 (3.16) на число Q, причем в левой части произведем деление, пользуясь правилами Р-ичной арифметики (так как запись числа N в Р-ичной системе счисления известна), а правую часть перепишем в виде N/Q = q s Q s + q s-1 Q s-1 +…+ q 1 Q 1 +q 0 / Q. Приравнивая между собой полученные целые и дробные части (учитывая, что q i < Q): [N/Q] = q s Q s-1 + q s-1 Q s-2 +…+ q 1 , [N/Q]=q 0 /Q. 101 Таким образом, младший коэффициент q 0 в разложении (3.16) определяется соотношением Q 0 =Q[N/Q], причем указанные здесь действия на самом деле не выполняются, так как q 0 является просто остатком от деления N на Q. Положим N 1 =[N/Q]= q s Q s-1 + q s-1 Q s-2 +…+ q 1 Тогда N 1 будет целым числом и к нему можно применить ту же самую процедуру для определения следующего коэффициента q 1 и т.д. Таким образом, при условии что N 0 = N, перевод чисел с использованием Р-ичной арифметики осуществляется по следующим рекуррентным формулам: q i = Q[N i / Q], (3.17) N i+1 = [N i / Q] (i=0, 1, 2). Этот процесс продолжается до тех пор, пока не будет получено N i+1 =0. Заметим, что поскольку все операции выполняются в системе счисления с основанием Р, то в этой же системе будут получены искомые коэффициенты q i , поэтому их необходимо записать одной Q-ичной цифрой. 2. Перевод дробных чисел. Пусть необходимо перевести в Q-ичную систему счисления правильную дробь х (0 < х < 1 ), заданную в Р-ичной системе счисления. Так как х < 1, то число х в Q-ичной системе счисления можно представить в виде полинома x = q -1 Q -1 + q -2 Q -2 + … + q -m Q -m +…, (3.18) где q -i (i = 1, 2, ...) - искомые коэффициенты Q-ичного разложения числа х. Для определения q -1 умножим обе части равенства (3.18) на число Q, причем в левой части произведем умножение, пользуясь правилами Р-ичной арифметики (так как запись числа x в Р-ичной системе счисления известна), а правую часть перепишем в виде xQ = q -1 + q -2 Q -1 + q -m Q -m +… . Приравняем между собой полученные в правой части этого выражения целые и дробные части (учитывая, что 0 < q i < Q): [xQ]=q -1 , [xQ]=q -2 Q -1 + … + q -m Q -m+1 +… . Таким образом, младший коэффициент q -1 в разложении (3.18) определяется соотношением q -1 = [x i Q]. Положим, x 1 = [xQ] = q -2 Q -1 +…+ q -m Q -m+1 +… . 102 Тогда x 1 будет правильной дробью и к этому числу можно применить ту же самую процедуру для определения следующего коэффициента q -2 и т.д. Таким образом, при условии, что x 0 =x, перевод дроби с использованием Р-ичной арифметики осуществляется по следующим рекуррентным формулам: q -(i+1) = [x i Q], x i+1 = [x i Q] (i=0,1,2,…). (3.19) Этот процесс продолжается до тех пор, пока не будет получено x i+1 =0 или не будет достигнута требуемая точность изображения числа. Замечание. При переводе приближенных дробей из одной системы счисления в другую необходимо придерживаться следующего правила. Если единица младшего разряда числа х, заданного в Р-ичной системе счисления, есть P -k , то в его Q-ичной записи следует сохранить z разрядов после запятой, где z удовлетворяет условию Q -z > P -k /2 > Q -(z+1) , округляя последнюю оставляемую цифру обычным способом. Приведем примеры перевода чисел из одной системы счисления в другую методом деления. Для перевода десятичного числа в двоичную систему его необходимо последовательно делить на 2 до тех пор, пока не останется остаток, меньший или равный 1. Число в двоичной системе записывается как последовательность последнего результата деления и остатков от деления в обратном порядке. Пример. Число 22 10 перевести в двоичную систему счисления. 22 10 = 10110 2 Для перевода десятичного числа в восьмеричную систему его необходимо последовательно делить на 8 до тех пор, пока не останется остаток, меньший или равный 7. Число в восьмеричной системе записывается как последовательность цифр последнего результата деления и остатков от деления в обратном порядке. Пример. Число 571 10 перевести в восьмеричную систему счисления. 571 10 = 1073 8 _571 56 _ _11 8 3 8 _71 64 7 8 _8 8 0 8 1 22 22 0 2 11 10 1 2 5 4 1 2 2 2 0 2 1 103 Для перевода десятичного числа в шестнадцатеричную систему его необходимо последовательно делить на 16 до тех пор, пока не останется остаток, меньший или равный 15. Число в шестнадцатеричной системе записывается как последовательность цифр последнего результата деления и остатков от деления в обратном порядке. Пример. Число 7467 10 перевести в шестнадцатеричную систему счисления. 7467 10 = 1D2B 16 3.5 Представление данных в компьютере Представление целых чисел без знака и со знаком Введем основные понятия на примере 4-битовых машинных слов. Такой размер слова обеспечивает хранение десятичных чисел только от 0 до 15 и поэтому не представляет практического значения. Однако они менее громоздки, а основные закономерности, обнаруженные на примере 4- битовых слов, сохраняют силу для машинного слова любого размера. Предположим, что процессор ЭВМ способен увеличивать (прибавлять единицу) и дополнять (инвертировать) 4-битовые слова. Например, результатом увеличения слова 1100 является 1101, а результатом дополнения этого слова является 0011. Рассмотрим слово 0000, представляющее десятичное число 0. В результате увеличения содержимое этого слова станет равным 0001, что соответствует десятичному числу 1. Продолжая последовательно увеличивать 4-битовые слова, придем к ситуации, когда, увеличивая слово 1111 (которое представляет десятичное число 15), получим в результате слово 0000, т. е. 111+1 = 0000 (15+1=0), при этом получили неверную арифметическую операцию и вернулись в исходное состояние. Это произошло из-за того, что слово памяти может состоять только из конечного числа битов. Таким образом, числовая система ЭВМ является конечной и цикличной. Такой ситуации, приводящей к неверному арифметическому результату, можно избежать, если битовую конфигурацию 1111 принять за код для -1. Тогда 1110 интерпретируется как -2; 1101 – 3 и т.д. до 1000 – 8. Тем самым получили другую числовую систему – со знаком, содержащую как положительные, так и отрицательные числа. В этой системе половина четырехбитовых конфигураций, начинающаяся с единицы, интерпретируется как отрицательные числа, а другая половина, начинающаяся с 0, – как положительные числа или нуль. Поэтому старший бит числа (третий по 7467 7456 11 16 466 464 2 16 29 16 13 16 1 104 счету, если нумерацию битов начинать с нуля справа налево) называется знаковым битом. Числовая система со знаком также конечна и циклична, однако в этом случае арифметически неверный результат даст попытка увеличить число 8 на единицу. Преимущество введения числовой системы со знаком заключается в возможности представления как положительных, так и отрицательных чисел. Если знаковый бит равен нулю, то значение числа легко вычисляется - игнорируется знаковый бит, а оставшиеся три бита интерпретируются как двоичный код десятичного числа. Например, слово 0110 представляет двоичное число 110, которое равно десятичному числу 6. Для оценки отрицательного числа нужно изменить его знак. Рассмотрим четырехбитовое число k в системе со знаком. Тогда –k = (-1-k)+1, следовательно, для вычисления значения - k необходимо вычесть k из -1 (т.е. из 1111) и затем прибавить 1 (т.е. 0001). Заметим, что операция вычитания всегда возможна, никогда не требует заема и равнозначна операции инвертирования битов вычитаемого. Например, 1111 - 1011 = 0100, здесь в вычитаемом, равном 1011, единицы перешли в нули, а нуль - в единицу. Инвертирование битов в слове называется дополнением до единицы. Для определения отрицательного значения числа k надо к его дополнению до единицы прибавить единицу (согласно вышеприведенному равенству). Инвертирование битов в слове с добавлением единицы к младшему биту называется дополнением до двух. Например, требуется найти, какое число закодировано в слове 1001. Для этого сначала выполняем операцию инвертирования 1001 0110, а затем к полученному результату прибавляем единицу 0110+1 = 0111, что является двоичным кодом числа 7. Таким образом, значением 1001 является отрицательное 7, т.е. -7. Индикаторы переноса и переполнения Рассмотрим более подробно ситуацию, приводящую при увеличении четырехбитового числа (т.е. прибавления к нему 1) к неверному арифметическому результату, возникшую из-за конечности числовой системы ЭВМ. В числовой системе без знака эта проблема возникает при увеличении слова 1111, при этом имеет место перенос единицы из знакового бита. В случае системы чисел со знаком перенос из старшего бита дает верный результат: 1111+ 0001 = 0000 (что правильно: -1 + 1 = 0 ). Но в этой системе увеличение слова 0111 приводит к ошибочной ситуации: 0111 + 1 = 1000 (7 + 1 = -8), при этом имеет место перенос в знаковый бит. В арифметико-логическом устройстве (АЛУ) процессора ЭВМ содержатся два индикатора - индикатор переноса и индикатор переполнения. Каждый индикатор содержит 1 бит информации и может быть процессором установлен (в этом случае ему придается значение, равное 1) или сброшен (равен 0). Индикатор переноса указывает на перенос из знакового бита, а индикатор переполнения - на перенос в знаковый бит. Таким образом, после завершения операции, в которой происходит перенос в старший бит, 105 процессор устанавливает индикатор переполнения, если такого переноса нет, то индикатор переполнения сбрасывается. Индикатор переноса обрабатывается аналогичным образом. Важно то, что после выполнения операции процессором, ЭВМ сигнализирует о состоянии индикаторов и их можно проверить. Если состояние индикаторов указывает на неправильный арифметический результат, то необходимо предпринять меры, исправляющие эту ситуацию, т.е. пользователю ЭВМ предоставляется возможность контролировать правильность выполнения арифметических операций. Следует иметь в виду, что способ обработки индикаторов процессором (т.е. их установление или сброс) зависит от выполняемой операции, а не просто от того, были или нет переносы. В одних случаях установка индикаторов будет происходить так, как описано выше. В других случаях один или другой индикатор может быть установлен или сброшен независимо от того, происходил ли в действительности перенос в знаковый бит или из него, или есть случаи, когда индикаторы остаются без изменения. Таким образом, правила для условий, при которых индикаторы устанавливаются, сбрасываются или остаются без изменения, зависят от выполняемой операции. При конструировании ЭВМ эти условия учитываются, и аппаратура разрабатывается таким образом, чтобы индикаторы переноса и переполнения давали информацию о правильности выполнения операций в целом ряде обстоятельств. Например, правильность операции сложения определяется на основании следующих условий: 1. Если машинные слова интерпретируются как числа без знака, то результат сложения двух слов будет арифметически правильным тогда и только тогда, когда не будет переноса из знакового бита. 2. Если машинные слова интерпретируются как числа со знаком, то результат сложения а) двух положительных чисел будет арифметически правильным тогда и только тогда, когда не будет переноса в знаковый бит; б) двух отрицательных чисел будет арифметически правильным тогда и только тогда, когда будет происходить перенос в знаковый бит, причем в этой ситуации перенос из знакового бита происходит всегда; в) отрицательного и положительного чисел всегда будет правильным, а перенос в знаковый бит будет происходить тогда и только тогда, когда будет также происходить перенос из знакового бита. Таким образом, если в результате выполнения операции сложения происходит перенос из знакового бита, то индикатор переноса устанавливается, если нет, то индикатор переноса сбрасывается, т.е. состояние индикатора переноса, сброшенное или установленное, показывает соответственно правильность или неправильность операции сложения без учета знака. Индикатор переполнения устанавливается, если два складываемых числа имеют один и тот же знак, а результат сложения получается с противоположным знаком; в противном случае он 106 сбрасывается, т.е. индикатор переполнения устанавливается тогда и только тогда, когда происходит только один из переносов в знаковый бит или из него. Тем самым состояние индикатора переполнения (сброшенное или установленное) может использоваться для определения соответственно правильности или неправильности сложения с учетом знака. Пример 1. Рассмотрим сложение двух чисел 0101+0011=1000. В результате выполнения операции сложения произошел перенос в знаковый бит, а переноса из знакового бита не было. Таким образом, после завершения этой операции индикатор переноса будет сброшен, а индикатор переполнения установлен. Поэтому если рассматривать эти два числа как целые без знака, то результат является арифметически правильным, так как индикатор переноса сброшен. Если рассматривать числа в системе со знаком, то бит переполнения показывает, что произошло изменение знака (перенос в знаковый бит есть, а из – нет), поэтому арифметический результат неправильный. Пример 2. В результате сложения 1101+0101=0010 происходит перенос и в знаковый бит, и из знакового бита. Поэтому будет установлен индикатор переноса, а индикатор переполнения сброшен. Следовательно, в системе чисел без знака результат является арифметически неправильным, а в системе чисел со знаком – правильным. Пример 3. В результате сложения 0011+0010=0101 не происходит переноса ни в знаковый бит, ни из него. Поэтому оба индикатора будут сброшены. Следовательно, в этом случае в обеих числовых системах (без знака и со знаком) результат будет арифметически правильным. Операцию вычитания можно свести к операции сложения в силу того, что А–В=А+(–В). Таким образом, необходимо только над вычитаемым произвести операцию дополнения до двух и сложить его с уменьшаемым. Например, операция 0011-1001 эквивалентна операции 0011+(0110+1)=0011 + 0111 = 1010. В этом случае в системе чисел без знака (3 - 9 = 10) и со знаком (3-(-7) = -6) результат является арифметически неправильным. Правильность или неправильность результатов вычитания, так же как и при сложении, зависит от того, происходили (или нет) переносы в знаковый бит или из него. Чтобы понять, как процессор устанавливает индикаторы переноса и переполнения, надо помнить, что вычитание выполняется как сложение: А-В=А+(-В). Если это сложение приводит к переносу из знакового бита, то индикатор переноса сбрасывается, иначе он устанавливается. Следовательно, в случае вычитания индикатор переноса устанавливается обратно тому, как при сложении. Индикатор переполнения устанавливается, если уменьшаемое и вычитаемое имеют противоположные знаки (т.е. имеют разные знаковые биты), а результат вычитания имеет тот же знак, что и вычитаемое, то индикатор переполнения сбрасывается. Таким образом, состояние индикатора переноса (сброшен или установлен) показывает соответственно на правильность и неправильность вычитания в числовой системе без учета знака, а сброшенный или установленный индикатор переполнения показывает соответственно на 107 правильность или неправильность вычитания в числовой системе со знаком. При этом индикатор переноса устанавливается тогда и только тогда, когда нет переноса из знакового бита, а индикатор переполнения устанавливается тогда и только тогда, когда был только один перенос в знаковый бит или из него. Пример 4. В результате выполнения операции вычитания 1001-0011 = =1001+(-0011)=1001+(1100+1)=1001+1101=0110 происходит перенос из знакового бита, а переноса в знаковый бит нет. Следовательно, индикатор переноса будет сброшен, а индикатор переполнения установлен, что указывает на то, что в данном примере в системе без знака результат арифметически правильный, а в системе со знаком – неправильный. |