Информатика двоичная арифметика примеры. Формальные правила двоичной арифметики. Раздел «Информация и информационные процессы»
Цель работы. Научиться выполнять арифметические операции (сложение, вычитание, умножение и деления) с двоичными числами.
Правила выполнения арифметических действий над двоичными числами задаются таблицами двоичных сложения, вычитания и умножения.
|
Таблица двоичного сложения |
Таблица двоичного вычитания |
Таблица двоичного умножения |
|
01=0 10=0 11=1 |
Задание 1. Выполните сложение чисел в двоичной системе счисления 100100111,001 2 +100111010,101 2
Методические указания.
При сложении двоичных чисел в каждом разряде производится сложение цифр слагаемых и цифры, переносимой из соседнего младшего разряда, если она имеется При этом необходимо учитывать, что 1+1 дают нуль в данном разряде и единицу переноса в следующий разряд.
Примеры .
1) Выполнить сложение двоичных чисел X=1101, Y=111.
В приведенном примере в младшем нулевом разряде две единицы: 1+1=10 дают нуль в данном разряде и единицу переноса в следующий. В первом разряде: 0+1+1=10 (крайняя единица перенесена из нулевого разряда) дают 0 и единицу переноса в следующий. Во втором разряде 1+1+1=11(крайняя единицы перенесена из первого разряда) дают 1 и единицу переноса в следующий. В старшем третьем разряде 1 и единица переноса из предыдущего разряда дают 1+1=10.
Результат: 1101+111=10100.
2) Сложить три двоичных числа X=1101, Y=101, Z=111.
Результат: 1101+101+111=11001.
Задание 2. Выполните вычитание чисел в двоичной системе счисления: 1100110110,0011 2 – 11111110,01 2 .
Методические указания.
При вычитании двоичных чисел в данном разряде при необходимости занимается 1 из старшего разряда. Эта занимаемая 1 равна двум единицам данного разряда, так как 10=1+1.
Примеры .
1) Заданы двоичные числа X=10010 и Y=101. Вычислить X–Y.
Результат: 10010 2 – 101 2 = 1101 2 .
Замечание. Число 100…00 2 можно представить в виде суммы
Данное разложение на слагаемые объясняет правило вычитания в столбик. Если вы занимаете 1 из ближайшего старшего разряда, тогда над всеми следующими за единицей нулями следует дописывать 1, а над крайним нулем, для которого произведен заем, 1+1 или 10.
2) Выполнить вычитание: 1100000011,011 2 – 101010111,1 2
Результат: 1100000011,011 2 – 101010111,1 2 = 110101011,111 2 .
Задание 3. Выполните умножение чисел 11001 2 и 1011100 2 в двоичной системе счисления.
Методические указания.
Правила умножения двоичных чисел такие же, как и для умножения десятичных чисел в столбик, с использованием двоичного умножения и сложения.
Пример . Найти произведение 1001 2 101 2
101
Результат: 1001 2 101 2 =101101 2 .Задание 4. Выполните деление чисел 111101 2 и 1110 2 в двоичной системе счисления.
Методические указания.
Деление двоичных чисел производится так же, как и десятичных чисел, при этом используется двоичное умножение и вычитание.
Пример . Найти частное от деления 1100, 011 2 : 10, 01 2
Результат: 1100, 011 2 : 10, 01 2 =101, 1 2 .
Задания для самостоятельной работы
|
Заданы двоичные числа X и Y. Вычислить X+Y и X–Y , если: |
Заданы двоичные числа X и Y. Вычислить X*Y и X/Y , если: |
|
|
Х=100101,101 2 Y=11101,11 2 |
X=100101,011 2 Y=110,1 2 |
|
|
Х=101101,101 2 Y=1101,111 2 |
X=110000,11 2
Y= |
|
|
Х=110101,101 2 Y=11101,11 2 |
X=111001,0001 2 Y=1010,011 2 |
|
|
Х=1101111,101 2 Y=10101,11 2 |
X=111011,0001 2 Y=101,01 2 |
|
|
Х=1000111,11 2 Y=11101,111 2 |
X=111100,011 2 Y=101,11 2 |
|
|
Х=1110001,101 2 Y=10011,11 2 |
X=110110,101 2 Y=100,11 2 |
|
|
Х=1010001,101 2 Y=10011,11 2 |
X=100110,0001 2 Y=111,01 2 |
|
|
Х=1000011,101 2 Y=10011,011 2 |
X=101011,111 2 Y=110,11 2 |
|
|
Х=1101001, 101 2 Y=10111,11 2 |
X=1010110,101 2 Y=1000,01 2 |
|
|
Х=1010001,101 2 Y=1111,011 2 |
X=111111,01 2 Y=101,1 2 |
|
|
Х=101001, 101 2 Y=10111,111 2 |
X=1011010,101 2 , Y=111,01 2 |
|
|
Х=1010111, 101 2 Y=11100,111 2 |
X=1000101,0011 2 , Y=110,11 2 |
|
|
Х=110101,101 2 Y=1111,11 2 |
X=100101,011 2 , Y=110,1 2 |
|
|
Х=101111,101 2 Y=1101,111 2 |
X=100000,1101 2 , Y=101,01 2 |
|
|
Х=110101,011 2 Y=10011,11 2 |
Х=110111,11 2 Y=101,11 2 |
|
|
Х=1001011,11 2 Y=10101,101 2 |
Х=100101,11 2 Y=111,01 2 |
|
|
Х=100011,011 2 Y=10011,111 2 |
Х=100011,01 2 Y=1011,1 2 |
|
|
Х=1010001,101 2 Y=1011,011 2 |
Х=100001,101 2 Y=1001,01 2 |
|
|
Х=110001,101 2 Y=10111,11 2 |
Х=111001,101 2 Y=1101,11 2 |
|
|
Х=1000111,011 2 Y=11111,11 2 |
Х=1010111,011 2 Y=111,11 2 |
|
|
Х=111001, 101 2 Y=1110,111 2 |
Х=11100001, 101 2 Y=110,11 2 |
|
|
Х=100001,101 2 Y=1111,111 2 |
Х=1000001,101 2 Y=1111,01 2 |
|
|
Х=1011101, 101 2 Y=10111,011 2 |
Х=1010101, 101 2 Y=100,011 2 |
|
|
Х=1111000, 101 2 Y=101111,11 2 |
Х=1111001, 011 2 Y=1011,11 2 |
|
|
Х=1100000, 101 2 Y=1111,111 2 |
Х=1100011, 01 2 Y=11,111 2 |
Контрольные вопросы.
1. Каковы правила сложения двоичных чисел?
2. Каковы правила вычитания двоичных чисел?
3. Каковы правила умножения двоичных чисел?
4. Каковы правила вычитания двоичных чисел?
Арифметические операции над двоичными числами осуществляются с помощью алгоритма под названием «сложение в столбик». Правила выполнения арифметических действий над двоичными числами задаются таблицами двоичных сложения, вычитания и умножения (табл. 1.31).
Таблица 1.31. Арифметические операции над двоичными числами
Пр и мер 1.60. Произвести сложение чисел 55,25 и 19,5 в десятичной и в двоичной системах счисления.
Первое слагаемое 55 , 25 1 1 0 1 1 1,0 1
Второе слагаемое 19 , 50 1 0 0 1 1,1 0
Образующийся дополнительный бит называется битом переноса.
Пр и мер 1.61. Произвести сложение чисел 65 и 42 в двоичной системе счисления.
- 65 10 = 01000001 2 .
- 42 10 = 00101010 2 .
Выполним сложение этих чисел:
01000001 Первое слагаемое
00101010 Второе слагаемое 01101011 Результат
Можно убедиться, что (01101011) 2 = (107) 10:
0 2 7 + 1 2 6 + 1 2 5 + 0 2 4 + 1 -2 3 + 0-2 2 + 1 -2" + 1 -2° = = 64 + 32 + 8 + 2+ 1 = 107.
Пр и мер 1.62. Выполнить сложение двоичных чисел X и У. а) Х= 1101; У= 101.
|
Х+ У = |
Результат. 1101 + 101 = 10010. б)Х= 1101; У= 101; 7= 111.
х+у+г= 110 0 1
Примечание. Вычитание чисел в двоичной системе счисления выполняется так же, как и в десятичной. При необходимости занимается единица из следующего старшего разряда, причем занимаемая единица равна двум единицам данного разряда. Заем единицы производится каждый раз, когда цифра в разряде вычитаемого количественно больше цифры в том же разряде уменьшаемого. Для выполнения операции вычитания она заменяется сложением, а в качестве второго слагаемого берется инвертированное (противоположное) число. Например, пусть нужно выполнить вычитание: 65 - 42. Заменим его сложением: 65 + (-42).
Назначение сервиса . Онлайн-калькулятор предназначен для сложения двоичных чисел в прямом, обратном и дополнительном кодах.Вместе с этим калькулятором также используют следующие:
Перевод чисел в двоичную, шестнадцатеричную, десятичную, восьмеричную системы счисления
Умножение двоичных чисел
Формат представления чисел с плавающей запятой
Пример №1
. Представить число 133,54 в форме числа с плавающей точкой.
Решение
. Представим число 133.54 в нормализованном экспоненциальном виде:
1.3354*10 2 = 1.3354*exp 10 2
Число 1.3354*exp 10 2 состоит из двух частей: мантиссы M=1.3354 и экспоненты exp 10 =2
Если мантисса находится в диапазоне 1 ≤ M Представление числа в денормализованном экспоненциальном виде
.
Если мантисса находится в диапазоне 0,1 ≤ M Представим число в денормализованном экспоненциальном виде: 0.13354*exp 10 3
Пример №2
. Представить двоичное число 101.10 2 в нормализованном виде, записать в 32-битом стандарте IEEE754.
Таблица истинности
Вычисление пределов
Арифметика в двоичной системе счисления
Арифметические действия в двоичной системе выполняются так же, как и в десятичной. Но, если в десятичной системе счисления перенос и заём осуществляется по десять единиц, то в двоичной - по две единицы. В таблице представлены правила сложения и вычитания в двоичной системе счисления.- При сложении в двоичной системе системе счисления двух единиц в данном разряде будет 0 и появится перенос единицы в старший разряд.
- При вычитании из нуля единицы производится заём единицы из старшего разряда, где есть 1 . Единица, занятая в этом разряде, даёт две единицы в разряде, где вычисляется действие, а также по единице, во всех промежуточных разрядах.
Сложение чисел с учетом их знаков на машине представляет собой последовательность следующих действий:
- преобразование исходных чисел в указанный код;
- поразрядное сложение кодов;
- анализ полученного результата.
При выполнении операции в дополнительном (модифицированном дополнительном) коде если в результате сложения в знаковом разряде возникает единица переноса, она отбрасывается.
Операция вычитания в ЭВМ выполняется через сложение по правилу: Х-У=Х+(-У). Дальнейшие действия выполняются также как и для операции сложения.
Пример №1
.
Дано: х=0,110001; y= -0,001001, сложить в обратном модифицированном коде.
Дано: х=0,101001; y= -0,001101, сложить в дополнительном модифицированном коде.
Пример №2
. Решить примеры на вычитание двоичных чисел, используя метод дополнения до 1 и циклического переноса.
а) 11 - 10.
Решение
.
Представим числа 11 2 и -10 2 в обратном коде.
Двоичное число 0000011 имеет обратный код 0,0000011
Сложим числа 00000011 и 11111101
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | |||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | ||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 |
В 2-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 3-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | |||||
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | ||||
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | |||
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
В итоге получаем:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Возник перенос из знакового разряда. Добавим его (т.е. 1) к полученному числу (тем самым осуществляя процедуру циклического переноса).
В итоге получаем:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Результат сложения: 00000001. Переведем в десятичное представление . Для перевода целой части необходимо умножить разряд числа на соответствующую ему степень разряда.
00000001 = 2 7 *0 + 2 6 *0 + 2 5 *0 + 2 4 *0 + 2 3 *0 + 2 2 *0 + 2 1 *0 + 2 0 *1 = 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 1
Результат сложения (в десятичном представлении): 1
б) 111-010
Представим числа 111 2 и -010 2 в обратном коде.
Обратный код для положительного числа совпадает с прямым кодом. Для отрицательного числа все цифры числа заменяются на противоположные (1 на 0, 0 на 1), а в знаковый разряд заносится единица.
Двоичное число 0000111 имеет обратный код 0,0000111
Двоичное число 0000010 имеет обратный код 1,1111101
Сложим числа 00000111 и 11111101
В 0-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 1-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | |||||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 |
В 1-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 2-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | ||||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 |
В 2-ом разряде возникло переполнение (1 + 1 + 1 = 11). Поэтому записываем 1, а 1 переносим на 3-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | |||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 |
В 3-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 4-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | ||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 |
В 4-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 5-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | |||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 |
В 5-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 6-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | ||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 |
В 6-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 7-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 |
В 7-ом разряде возникло переполнение (1 + 1 = 10). Поэтому записываем 0, а 1 переносим на 8-й разряд.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
В итоге получаем:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
Возник перенос из знакового разряда. Добавим его (т.е. 1) к полученному числу (тем самым осуществляя процедуру циклического переноса).
В итоге получаем:
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
Результат сложения: 00000101
Получили число 00000101. Для перевода целой части необходимо умножить разряд числа на соответствующую ему степень разряда.
00000101 = 2 7 *0 + 2 6 *0 + 2 5 *0 + 2 4 *0 + 2 3 *0 + 2 2 *1 + 2 1 *0 + 2 0 *1 = 0 + 0 + 0 + 0 + 0 + 4 + 0 + 1 = 5
Результат сложения (в десятичном представлении): 5
Сложение двоичных вещественных чисел с плавающей запятой
В компьютере любое число может быть представлено в формате с плавающей точкой. Формат с плавающей точкой показан на рисунке:
Например, число 10101 в формате с плавающей точкой можно записать так:
В компьютерах используется нормализованная форма записи числа, в которой положение запятой всегда задается перед значащей цифрой мантиссы, т.е. выполняется условие:
b -1 ≤|M|Нормализованное число - это число, у которого после запятой идет значащая цифра (т.е. 1 в двоичной системе счисления). Пример нормализации:
0,00101*2 100 =0,101*2 10
111,1001*2 10 =0,111001*2 101
0,01101*2 -11 =0,1101*2 -100
11,1011*2 -101 =0,11011*2 -11
При сложении чисел с плавающей точкой выравнивание порядков выполняют в сторону большего порядка:
Алгоритм сложения чисел с плавающей точкой:
- Выравнивание порядков;
- Сложение мантисс в дополнительном модифицированном коде;
- Нормализация результата.
Пример №4
.
A=0,1011*2 10 , B=0,0001*2 11
1. Выравнивание порядков;
A=0,01011*2 11 , B=0,0001*2 11
2. Сложение мантисс в дополнительном модифицированном коде;
MA доп.мод. =00,01011
MB доп.мод. =00,0001
00,01011
+ 00,00010
=
00,01101
A+B=0,01101*2 11
3. Нормализация результата.
A+B=0,1101*2 10
Пример №3 . Записать десятичное число в двоично-десятичной системе счисления и сложить два числа в двоичной системе счисления.
Выполнение арифметических действий в любых позиционных системах счисления производится по тем же правилам, которые используются в десятичной системе счисления.
Так же, как и в десятичной системе счисления, для выполнения арифметических действий необходимо знать таблицы сложения (вычитания) и умножения.
Таблица сложения, вычитания и умножения для двоичной системы счисления
Сложение двоичных чисел
Сложение в двоичной системе счисления выполняется по тем же правилам, что и в десятичной. Два числа записываются в столбик с выравниванием по разделителю целой и дробной части и при необходимости дополняются справа незначащими нулями. Сложение начинается с крайнего правого разряда. Две единицы младшего разряда объединяются в единицу старшего.
Пример
: 1011,1 2 + 1010,11 2
Интересна также ситуация, когда складываются больше двух чисел. В этом случае возможен перенос через несколько разрядов.
Пример
: 111,1 2 + 111 2 + 101,1 2
При сложении в разряде единиц (разряд 0) оказывается 4 единицы, которые, объединившись, дают 100 2
. Поэтому из нулевого разряда в первый разряд переносится 0
, а во второй — 1
.
Аналогичная ситуация возникает во втором разряде, где с учетом двух перенесенных единиц получается число 5 = 101 2
. 1
остается во втором разряде, 0
переносится в третий и 1
переносится в четвёртый.
Вычитание двоичных чисел
В случаях, когда занимается единица старшего разряда, она дает две единицы младшего разряда. Если занимается единица через несколько разрядов, то она дает по одной единице во всех промежуточных нулевых разрядах и две единицы в том разряде, для которого занималась.
Пример
: 10110,01 2 — 1001,1 2
роизвольное натуральное число можно единственным способом представить в виде суммы степеней двойки, например 23 = 16+4+2+1. Обозначая входящие в эту сумму степени двойки единицами, а не входящие в ее степени нулями, можно кратко обозначить эту сумму булевым набором (в другой терминологии - вектором) (10111) 2 . Индекс 2 напоминает о том, что число записано в двоичной системе. Единица, стоящая в младшем (самом левом) разряде, означает слагаемое 1, единица во втором слева разряде означает слагаемое 2, единица в третьем разряде означает 4, а нуль в четвертом разряде означает отсутствие слагаемого 8, единица в четвертом (старшем) разряде означает присутствие слагаемого 16 (в большинстве случаев разумно рассматривать только такие записи чисел в двоичной системе, в которых в старшем разряде стоит единица).
Главное достоинство двоичной системы (помимо естественности ее применения в электронной цифровой технике) - исключительная простота алгоритмов арифметических операций в ней. Таблица умножения в двоичной системе совсем не требует запоминания: любое число, умноженное на нуль дает нуль, а умноженное на единицу равно самому себе. Правило деления сводится к двум равенствам 0/1 = 0, 1/1 =1, благодаря чему деление столбиком в двоичной системе делается проще, чем в десятичной, и по существу сводится к многократному вычитанию. Таблица сложения в двоичной системе чуть сложнее таблицы умножения (в отличие от десятичной системы), так как 1+1 = (10) 2 и возникает перенос в следующий разряд.
Правило сложения двух битов в двоичной системе задается формулами x+y = 2v+u, v = x&y, u = xÅy. В силу симметрии для их проверки достаточно рассмотреть не четыре, а три случая: 0+0 = (00) 2 , 1+0=0+1= (01) 2 , 1+1 = (10) 2 . Схема, выполняющая это сложение, называется полусумматором (в англоязычной литературе: half adder) и обозначается обычно HA или FA2. Эта схема (в базисе {AND, XOR}) изображена на рисунке.
Схемы для арифметических операций над многоразрядными двоичными числами. Сложение двух n-разрядных двоичных чисел (x n ,….,x 1) 2 и (y n ,….,y 1) 2 как и в десятичной системе приводит к появлению переносов в следующий разряд, которые необходимо учитывать в вычислении. Эти переносы также равны нулю или единице (если перенос равен нулю, то в ручном вычислении он фактически не выполняется, но логическая схема обязана правильно работать и в этом случае, ведь она «не знает», какой перенос пришел из предыдущего разряда). Обозначим перенос из (i-1)-го разряда в следующий i-й разряд через w i (w 1 =0, потому что предыдущего разряда в этом случае просто нет). Тогда для вычисления z i (i-го бита результата) нужно сложить биты x i и y i и бит переноса w i . Это сложение выполняем по формулам
x i + y i +w i = 2v i +u i , v i =m(x i ,y i ,w i), u i =l(x i ,y i ,w i)
с помощью схемы FA3. Тогда z i =u i =l(x i ,y i ,w i), а следующий бит переноса w i +1 = v i =m(x i ,y i ,w i). При сложении n-разрядных чисел получается вообще говоря n+1-разрядное число. Его старший бит z n +1 = w n +1 равен последнему переносу.
Схема сложения трехразрядных чисел приведена на следующем рисунке. Аналогичным образом выглядит и схема сложения n-разрядных чисел.
Сложность указанного n-разрядного сумматора равна 5n-3. Н.П.Редькин доказал, что сумматоров для n-разрядных чисел меньшей сложности в базисе {AND,OR,XOR,NOT} не существует. Построенный сумматор является поэтому минимальной схемой. Но у этой схемы есть существенный недостаток - она имеет большую глубину. Глубиной схемы называется максимальное число ее элементов, образующих цепь, соединяющую какой-либо из входов схемы с одним из ее выходов. Например, глубина указанной выше схемы FA3 равна 3.
Глубина схемы - не менее важная характеристика схемы, чем ее сложность. Сложность логической схемы в значительной степени определяет площадь соответствующей реальной схемы, расположенной на кремниевом кристалле. Глубина же логической схемы в значительной мере определяет задержку реальной схемы, т.е. время, за которое сигнал проходит от входов схемы к ее выходам, другими словами, время, которое должно пройти после стабилизации каких-либо значений на входах схемы до того момента, когда на всех выходах схемы также стабилизируются определенные логические значения. Сложность схемы часто не имеет существенного значения, так как современные технологии позволяют разместить на кристалле очень большие схемы. А минимизация задержки схемы очень важна, так как задержка комбинационной части многотактной схемы определяет ее тактовую частоту - чем меньше задержка, тем выше частота.
Теоретически вычислить задержку реальной схемы очень сложно. Цепей элементов схемы, соединяющих ее входы с выходами (эти цепи также называют путями), обычно довольно много и задержка схемы определяется задержкой по самому плохому в определенном смысле пути, который называется критическим. Например, на схеме FA3 критический путь, вероятно, соединяет входы X или Y с выходом m. Задержка по любому пути определяется не только суммой задержек всех элементов, лежащих на этом пути (в приведенном примере она равна 3, если считать задержку каждого элемента единичной). Следует учитывать также задержку соединяющих эти элементы проводов. Задержка элемента зависит от того, между каким его входом и каким его выходом она измеряется, а также от электрических характеристик самого элемента и элементов непосредственно с ним связанных в рассматриваемой схеме, она зависит от температуры схемы и даже от того, какие логические значения подаются в рассматриваемый момент на входы этого элемента и изменяется ли (и в какую сторону) значение на его выходе. Тем не менее, хотя и не очень точно, задержку пути можно оценить как сумму задержек его элементов. Если задержки всех элементов равны, то эта величина определяется глубиной схемы. Разумеется, понятие глубины схемы можно расширить, допустив, что элементы базиса могут иметь произвольные неотрицательные задержки.
Глубина указанной выше схемы n-разрядного сумматора на первый взгляд равна 3n-2. Но внимательный анализ возможных критических путей показывает, что она на самом деле равна 2n-1. Все равно это очень много и построенная таким образом реальная схема будет иметь большую задержку. На практике используются схемы, имеющие одновременно малую сложность, не превосходящую Cn (где С - небольшая константа) и малую глубину, приблизительно равную 2log 2 n. В.М. Храпченко в 1970 г. построил схему малой сложности и глубины, асимптотически равной log 2 n (т.е. равную (1+ e(n)) log 2 n, где e(n) стремится к нулю с ростом n). Он же недавно доказал, что глубина сумматора не может быть меньше log 2 n + log 2 n (log 2 (log 2 n))). Поэтому построенная им схема имеет асимптотически минимальную глубину. Однако схема Храпченко превосходит обычные схемы только при n порядка тысячи. Тем не менее существует некоторая модификация его схемы с глубиной приблизительно равной log j n, где j = (Ö5+1)/2, и эта схема имеет глубину меньшую, чем стандартные схемы, уже начиная с n = 8. В 2008 г. М.И.Гринчук построил схему глубины не большей log 2 n+log 2 (log 2 n)+6, которая уже при малых n имеет меньшую глубину, чем все известные схемы.
Задача построения оптимальных схем для умножения n-разрядных чисел оказалась еще труднее, чем задача о построении оптимальных сумматоров. Легко построить схему для умножения n-разрядных чисел в базисе {OR,AND,XOR,NOT} сложности приблизительно равной 6n 2 . Для этого можно использовать указанную выше схему для сумматора. Однако ее глубина будет велика. В начале 60-х годов несколько исследователей (в СССР Столяров и Офман, в США Авиценис и Уоллес) независимо построили схему для умножения сложности порядка n 2 и глубины порядка log 2 n. В смысле глубины эти схемы по порядку оптимальны, но до сих пор остается нерешенной задача построения схемы для умножения асимптотически минимальной глубины. В смысле сложности эти схемы оказались далеки от оптимальных. А. А. Карацуба построил в 1962 г. схему для умножения, имеющую сложность по порядку не большую n 1,6 , потом А. Л. Тоом построил схему сложности n 1+ e(n) , где e(n) стремится к нулю с ростом n. В определенном смысле этот результат окончательный, тем не менее он был уточнен на рубеже 70-х годов немецкими математиками А. Шенхаге и Ф. Штрассеном, которые получили для схем умножения верхнюю оценку сложности по порядку не превосходящую n log 2 n log 2 (log 2 n), а в 2008 г. эту оценку улучшил американский математик М. Фюрер, заменивший двойной логарифм крайне медленно растущей функцией. Есть предположение, что сложность схемы умножения по порядку не меньше n log 2 n, но и это не доказано.
Американский математик С.Кук доказал, что можно построить схему для деления 2n-разрядного числа на n-разрядное, у которой сложность по порядку не превосходит сложности умножения n-разрядных чисел. Известно также, что нижняя оценка сложности схемы для деления по порядку не меньше нижней оценки сложности умножения. Поэтому в смысле оценок сложности деление не представляет ничего нового в сравнении с умножением. Однако долгое время наилучшей оценкой глубины деления по порядку было (log 2 n) 2 .
Впоследствии были найдены схемы для деления с глубиной по порядку равной log 2 n, но их сложность оказалась велика. Американцы Рейф и Тейт построили схемы для деления глубины по порядку не превосходящей log 2 n log 2 (log 2 n) и одновременно сложности по порядку не превосходящей n log 2 n log 2 log 2 n, однако и эти схемы, как и схемы Шенхаге-Штрассена и Фюрера пока не нашли практических применений, так как в действительности начинают превосходить используемые на практике схемы лишь при огромных значениях n.
Рекомендуемая литература
- О.Б. Лупанов « Асимптотические оценки сложности управляющих систем » изд. МГУ, 1984.
- О.Б. Лупанов «Конспект лекций по математической логике »изд. МГУ, 2009.
- Дж. Сэвидж «Сложность вычислений » М. изд. Факториал, 1998.
- Д. Кнут « Искусство программирования на компьютере», т. 2, изд. Вильямс, 2000.
- С.Б. Гашков «Системы счисления и их применения », М. изд. МЦНМО, 2004.
- С.Б. Гашков, В.Н. Чубариков «Арифметика. Алгоритмы. Сложность вычислений », изд. Дрофа, 2005.
