Отнт. А. Ю. Босова Москва бином. Лаборатория знаний 10 класс Базовый уровень Учебник
 Скачать 6.18 Mb.
|
|
Глава3.представлениеинформациивкомпьютере 12.5. двоичная арифметика Арифметика двоичной системы счисления основывается на использовании следующих таблиц сложения, вычитания и умножения Рассмотрим несколько простых, но очень важных примеров на сложение и вычитание в двоичной системе счисления 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 + 1 1 1 1 1 1 2 – 1 0 0 0 0 2 – 1 0 1 0 1 0 2 1 1 1 1 1 2 1 0 0 0 0 0 0 2 1 1 1 1 1 0 0 0 1 1 Пример 1. Найдём количество единиц в двоичной записи числа, являющегося результатом десятичного выражения 2 4000 + 4 2016 + 2 2018 – 8 600 + Представим все операнды исходного выражения в виде степеней двойки 2016 = (2 · 2) 2016 = (2 2 ) 2016 = 2 2 · 2016 = 2 4032 , 8 600 = (2 3 ) 600 = 2 1800 , 6 = 4 + 2 = 2 2 + 2 Исходное выражение примет вид 2 4000 + 4 2016 + 2 2018 – 8 600 + 6 = 2 4000 + 2 4032 + 2 2018 – 2 1800 + 2 2 + 2 Перепишем выражение в порядке убывания степеней 2 4032 + 2 4000 + 2 2018 – 2 1800 + 2 2 + 2 Для работы с десятичными числами вида 2 n полезно иметь ввиду следующие закономерности в их двоичной записи 1 = 10 = 1 + 1; 2 2 = 100 = 11 + 1; 2 3 = 1000 = 111 + 1; 2 4 = 10000 = 1111 + 1 и т. д арифметические операции §12 В общем виде 10 0 1 1 1 n n n Для натуральных n и m таких, что n > m, получаем 2 10 0 10 0 10 0 10 0 1 n m n m n m m , 2 2 1 1 1 1 1 1 1 1 1 1 1 1 0 0 n m n m n m n m ( ) m m Эти соотношения позволят нам подсчитать количество единиц в нашем выражении, не прибегая к его вычислению. Действительно, двоичные представления чисел 2 4032 и 2 внесут в двоичное представление суммы по одной единице. Разность в двоичной записи представляет собой цепочку из 218 единиц и следующих за ними 1800 нулей. Слагаемые 2 и 2 1 дают ещё 2 единицы. Итого: 1 + 1 + 218 + 1 + 1 = Пример 2. Найдём количество цифр в восьмеричной записи числа, являющегося результатом десятичного выражения 2 299 + 2 298 + 2 297 + 2 Двоичное представление исходного числа имеет вид 11110 0 296 . Всего в этой записи 300 двоичных символов. При переводе двоичного числа в восьмеричную систему счисления каждая триада исходного числа заменяется восьмеричной цифрой. Следовательно, восьмеричное представление исходного числа состоит из 100 цифр. самое ГЛаВное Арифметические операции в позиционных системах счисления с основанием q выполняются по правилам, аналогичным правилам, действующим в десятичной системе счисления. Если необходимо вычислить значение арифметического выражения, операнды которого представлены в различных системах счисления, можно 1) все операнды представить в привычной нам десятичной системе счисления 2) вычислить результат выражения в десятичной системе счисления) перевести результат в требуемую систему счисления 128 Глава3.представлениеинформациивкомпьютере Для работы с десятичными числами вида 2 n полезно иметь ввиду следующие закономерности в их двоичной записи 10 0 1 1 1 n n n Для натуральных n и m таких, что n > m, получаем 2 10 0 10 0 10 0 10 0 1 n m n m n m m , 2 2 1 1 1 1 1 1 1 1 1 1 1 1 0 0 n m n m n m n m ( ) m m Вопросы и задания 1. Выполните арифметические операции над двоичными чис- лами: а) 10010011 + б) 110010,11 + в) 110101110 – г) 111110 · д) 11111100101 : 101011. Для того чтобы убедиться в правильности полученных результатов, найдите десятичные эквиваленты операндов и результата. Какое число следует за каждым из данных: а) 223 4 ; б) 677 8 ; в) 2222 3 ; г) 1001 2 ? Ответ для каждого числа дайте в указанной и десятичной системах счисления 3. Какое число предшествует каждому из данных: а) 222 3 ; б) 1000 5 ; в) 233 4 ; г) 1001 2 ? Ответ для каждого числа дайте в указанной и десятичной системах счисления 4. Сумму восьмеричных чисел 17 + 1700 + 170000 + 17000000 + + 1700000000 перевели в шестнадцатеричную систему счисления. Найдите в шестнадцатеричной записи числа, равного этой сумме, пятую цифру слева 5. Вычислите значение выражения: а) (1111101 2 + AF 16 ) : 36 б) 125 8 + 11101 2 · A2 16 – 1417 8 представление чисел в компьютере 6. Найдите среднее арифметическое следующих чисел: а) 10010110 2 , 1100100 2 и 110010 б) 226 8 , 64 16 и 62 8 7. В примерах на сложение восстановите неизвестные цифры, обозначенные знаком вопроса, определив вначале, в какой системе счисления эти числа записаны. а) + 2 ? 2 б ? 5 в 1 ? 0 2 1 2 3 ? ? 3 2 7 ? 1 2 1 2 ? 2 0 3 ? 1 6 ? 4 ? 2 ? 0 2 1 8. Даны 4 целых числа, записанные в двоичной системе счисления Сколько среди них чисел, больших, чем AB 16 + 25 8 ? 9. Сколько единиц в двоичной записи числа 4 2014 + 2 2015 – 9? 10. Сколько единиц в двоичной записи числа 8 4024 – 4 1605 + 2 1024 – 126? 11. Сколько цифр в восьмеричной записи числа 2 1024 + 2 1026 ? 12. Какая первая цифра в шестнадцатеричной записи числа 2 1024 + 2 1025 ? § представление чисел в компьютере Самым первым видом данных, с которыми начали работать компьютеры, были числа. ЭВМ первого поколения могли производить только математические расчёты (вычисления). Из курса информатики основной школы вы помните, что компьютеры работают с целыми и вещественными числами. Их представление в памяти осуществляется разными способами представление целых чисел Во многих задачах, решаемых на компьютере, обрабатываются целочисленные данные. Прежде всего, это задачи эконо- 130 Глава3.представлениеинформациивкомпьютере мического характера, при решении которых данными служат количества акций, сотрудников, деталей, транспортных средств и др. Целые числа используются для обозначения даты и времени, для нумерации различных объектов элементов массивов, записей в базах данных, машинных адресов и т. д. По своей природе множество целых чисел дискретно, т. к. состоит из отдельных элементов. И хотя любое целое число можно рассматривать как вещественное, нос нулевой дробной частью, предусмотрены специальные способы представления целых чисел. Это обеспечивает эффективное расходование памяти, повышение быстродействия, повышение точности вычислений за счёт введения операции деления нацело с остатком. Для компьютерного представления целых чисел используется несколько различных способов, отличающихся друг от друга количеством разрядов (под целые числа обычно отводится 8, 16, 32 или 64 разряда) и наличием или отсутствием знакового разряда. Беззнаковое представление можно использовать только для неотрицательных целых чисел. Для получения компьютерного представления беззнакового целого числа в разрядной ячейке памяти достаточно перевести его в двоичную систему счисления и, при необходимости, дополнить полученный результат слева нулями до n-разрядов. Например, десятичные числа 130 ив восьмиразрядном представлении будут иметь вид 0 0 0 0 0 1 0 0 0 1 0 0 1 1 Понятно, что существуют ограничения на числа, которые могут быть записаны в разрядную ячейку памяти. Максимальное значение целого неотрицательного числа достигается в случае, когда во всех разрядах ячейки хранятся единицы. Для разрядного представления оно будет равно 2 n É– 1. Минимальное число соответствует n нулям, хранящимся в n разрядах памяти, и равно нулю. Далее приведены диапазоны значений для беззнаковых целых разрядных чисел представление чисел в компьютере §13 Количество разрядов Диапазон чисел 255] 16 [0; 65 535] 32 [0; 4 294 967 295] 64 [0; 18 446 744 073 709 551 При знаковом представлении целых чисел старший разряд ячейки отводится под знак (0 — для положительных, 1 — для отрицательных чисел, а остальные разряды — под цифры числа. Представление числа в привычной для человека форме «знак–ве- личина, при которой старший разряд ячейки отводится под знака остальные разряды — под цифры числа, называется прямым кодом. Например, прямые коды чисел 48 и –52 для восьмиразрядной ячейки равны 0 1 1 0 0 0 0 1 0 1 1 0 1 0 Минимальное отрицательное число, которое можно записать в знаковом представлении в n разрядах, равно 2 n–1 . Максимальное положительное число, которое можно записать в знаковом представлении в n разрядах, равно 2 n–1 – 1. Ниже приведены диапазоны значений для знаковых представлений целых чисел в ячейках с различной разрядностью: Количество разрядов Диапазон чисел 127] 16 [–32 768; 32 767] 32 [–2 147 483 648; 2 147 483 647] 64 [–9 223 372 036 854 775 808; 9 223 372 036 854 775 807] 132 Глава3.представлениеинформациивкомпьютере В математике множество целых чисел бесконечно. Компьютер работает с ограниченным множеством целых чисел. Прямой код положительного числа отличается от прямого кода равного по абсолютной величине отрицательного числа только содержимым знакового разряда. В прямом коде числа можно хранить, но выполнение арифметических операций над числами в прямом коде затруднено — оно требует более сложной архитектуры центрального процессора, умеющего выполнять не только сложение, но и вычитание, а также знающего особый алгоритм обработки не имеющего веса знакового разряда. Этих трудностей позволяет избежать использование дополнительного кода. Чтобы понять сущность дополнительного кода, рассмотрим работу реверсивного счётчика, последовательность показаний которого можно представить в виде замкнутого кольца из чисел (рис. рис 3.5. Реверсивный счётчик При возрастании показаний счётчика до максимального, например до 999, следующими его состояниями должны быть 1000, 1001, 1002 и т. д. Но для изображения старшей единицы в счётчике не хватает разряда, происходит переполнение разрядной сетки. Поэтому мы увидим 000, 001, 002 и т. д. При убывании показаний счётчика после состояния 000 будут идти 999, 998, 997 и т. д. Но после достижения нуля последовательное вычитание единицы должно давать –1, –2, –3 и т. д. Будем рассматривать числа 999, 998, 997 как коды чисел –1, –2, –3 и проверим на их примере соотношение y + (–y) = 0: 001 + 999 = 1000; 002 + 998 = 1000; 003 + 997 = 1000. представление чисел в компьютере §13 С учётом того что единица переполнения теряется, мы, сложив число и код противоположного ему числа, получаем ноль! Вот ещё несколько примеров – 2 = 5 + [–2] = 5 + 998 = 1003; 7 – 5 = 7 + [–5] = 7 + 995 = Для устранения неоднозначности в кольце будем считать половину состояний (0–499) кодами нуля и положительных чисел, а оставшуюся половину (500–999) — кодами отрицательных чисел. Таким образом, дополнительный код положительного числа совпадает с этим числом, а для отрицательного числа он равен дополнению его величины до числа q n , возникающего при переполнении разрядной сетки. Здесь q — основание системы счисления, n — число разрядов в разрядной сетке. Рассмотрим алгоритм получения дополнительного разрядного кода отрицательного числа 1) модуль числа представить прямым кодом в n двоичных разрядах) значения всех разрядов инвертировать (все нули заменить единицами, а единицы — нулями 3) к полученному представлению, рассматриваемому как разрядное неотрицательное двоичное число, прибавить единицу. Пример 1. Найдём разрядный дополнительный код отрицательного числа –2017 Прямой код |–2017 10 | = 2017 10 00000111 11100001 Инвертирование 11111000 00011110 Прибавление единицы+ Дополнительный код 11111000 00011111 Использование дополнительного кода позволяет свести операцию вычитания чисел к операции поразрядного сложения кодов этих чисел. пример 2. Как известно, 48 – 2017 = Выполним эту операцию в разрядных машинных кодах. Нам потребуются прямой код числа 48 и дополнительный код числа Прямой код числа 48 00000000 00110000 Дополнительный код числа –2017 11111000 00011111 Поразрядное сложение кодов 01001111 2 134 Глава3.представлениеинформациивкомпьютере Рассмотрим полученный результат. Это отрицательное число об этом говорит 1 в знаковом разряде, представленное в дополнительном коде. Перейдём к прямому коду модуля соответствующего числа, по которому сможем восстановить десятичное представление результата. Прямой код можно получить из дополнительного кода, если применить к нему операцию инвертирования и прибавить единицу. Инвертирование 00000111 10110000 Прибавление единицы+ Прямой код модуля результата 10110001 Получаем –11110110001 2 = –1969. 13.2. представление вещественных чисел В математике множество вещественных чисел непрерывно, бесконечно и не ограничено. Попробуйте обосновать это утверждение. Вещественные числа записываются в естественной или в экспоненциальной форме. В жизни мы чаще пользуемся естественной формой записи чисел, при которой число представляется последовательностью десятичных цифр со знаком плюс или минус, знак плюс может опускаться, для разделения целой и дробной частей числа используется запятая. Например 12,34; 0,0056; В экспоненциальной форме вещественное число a представляется как a = ± m · q p , где m — мантисса числа, q — основание системы счисления, p — порядок числа. Например, длину некоторого отрезка, равного 47,8 см, можно записать так 1) 478 · 10 –1 см 2) 47,8 · 10 0 см 3) 4,78 · 10 1 см 4) 0,478 · 10 2 см 5) 0,000478 · 10 5 см представление чисел в компьютере §13 Такое многообразие вариантов записи в экспоненциальной форме одного итого же числа не всегда удобно. Для однозначного представления вещественных чисел в компьютере используется нормализованная форма. Нормализованная запись отличного от нуля вещественного числа — это запись вида a = ± m · q p , где p — целое число (положительное, отрицательное или ноль, m — дробь, целая часть которой содержит одну значащую (ненулевую) цифру, те Примеры нормализации чисел 1) 31,415926 = 3,1415926 · 10 1 ; 2) 1000 = 1,0 · 10 3 ; 3) 0,123456789 = 1,23456789 · 10 –1 ; 4) 0,0000107 8 = 1,07 8 · 10 –5 8 ; 5) 1000,0001 2 = 1,0000001 2 · 10 1 2 1 ; 6) AB,CDEF 16 = A,BCDEF 16 · 10 Диапазон вещественных чисел в памяти компьютера очень широк, но, тем не менее, ограничен. Множество вещественных чисел, которые могут быть представлены в компьютере, конечно. Поясним это на примере калькулятора, который производит вычисления в десятичной системе счисления. Пусть это будет калькулятор с десятью знакоместами на дисплее 6 знакомест отводится под мантиссу (одно знакоместо отводится под знак мантиссы, четыре под цифры мантиссы, одно — под точку, разделяющую целую и дробную части мантиссы одно знакоместо отводится под символ Е • три знакоместа отводятся под порядок (одно — под знак порядка, два — под цифры порядка Cтандарт IEEE 754. 136 Глава3.представлениеинформациивкомпьютере У калькуляторов первая значащая цифра, с которой и начинается мантисса, изображается перед точкой. Число 12,34 в таком калькуляторе будет представлено как +1.234Е+01. Число 12,35 будет представлено как +1.235Е+01. Как известно, между числами 12,34 и 12,35 находится бесконечное множество вещественных чисел, например 12,341; 12,3412; 12,34123 и т. д. Каждое из этих чисел в нашем калькуляторе будет представлено как +Е. Для последних разрядов у нас просто не хватает знакомест Аналогичная ситуация имеет место ив компьютерном представлении вещественных чисел, независимо оттого, ячейки какой разрядности там использованы. Получается, что точно мы можем представить в компьютере лишь некоторую конечную часть множества вещественных чисел, а остальные числа — лишь приближённо. Таким образом, множество вещественных чисел, представляемых в компьютере, дискретно, конечно и ограничено. самое ГЛаВное В математике множество целых чисел дискретно, бесконечно и не ограничено. Для компьютерного представления целых чисел используется несколько различных способов, отличающихся друг от друга количеством разрядов (8, 16, 32 или 64 разряда) и наличием или отсутствием знакового разряда. В любом случае компьютерное представление целых чисел дискретно, конечно и ограничено. В математике множество вещественных чисел непрерывно, бесконечно и не ограничено. Для компьютерного представления вещественных чисел используется нормализованная запись вещественного числа a = ± m · q p , где q — основание системы счисления, p — целое число (положительное, отрицательное или ноль, m — дробь, целая часть которой содержит одну значащую (ненулевую) цифру, те Компьютерное представление вещественных чисел дискретно, конечно и ограничено представление чисел в компьютере §13 Вопросы и задания 1. Представьте в восьмиразрядном формате прямые коды десятичных чисел: а) 64; б) 58; в) 72; г) –96. 2. Можно ли числа 43 16 , 101010 2 , 129 10 и –52 10 сохранить в однобайтовом формате 3. Как определяется диапазон представления в компьютере целых чисел без знака Со знаком 4. Почему множество целых чисел, представимых в памяти компьютера, дискретно, конечно и ограничено 5. Представьте в восьмиразрядном формате дополнительные коды двоичных чисел: а) +1010; б) –1001; в) –11; г) –11011. 6. Найдите десятичные эквиваленты чисел, представленных в прямом коде: а) 00000100; б) 00001001; в) 10000011; г) 10000110. 7. Найдите десятичные эквиваленты чисел, представленных в дополнительном коде: а) 00000100; б) 11111001. 8. Для хранения целого числа со знаком в компьютере используется два байта. Сколько единиц содержит внутреннее представление числа –101, записанного: а) в прямом коде; б) в дополнительном коде 9. Вычислите с помощью калькулятора (приложение Windows) в режиме Программист следующие примеры: а) 111011101 2 – 1101110110 б) 1101101001 2 – 11000100100 2 Как вы можете объяснить полученные результаты 10. Запишите десятичные числа в нормализованной форме: а) 217,934; б) 75321; в) 10,0101; г) 200450. 11. Сравните следующие числа: а) 318,4785 · 10 9 и 3,184785 · 10 б) 218,4785 · 10 –3 и 1847,85 · 10 –4 12. Выполните операцию сложения: а) 0,397621 · 10 3 + 0,2379 · 10 б) 0,251452 · 10 –3 + 0,125111 · 10 –2 13. Чем ограничивается диапазон представимых в памяти компьютера вещественных чисел 138 |