Дополнение - Ones' complement
| Биты | Беззнаковое значение |
Ones' комплемента значение |
|---|---|---|
| 0111 1111 | 127 | 127 |
| 0111 1110 | 126 | 126 |
| 0000 0010 | 2 | 2 |
| 0000 0001 | 1 | 1 |
| 0000 0000 | 0 | 0 |
| 1111 1111 | 255 | −0 |
| 1111 1110 | 254 | −1 |
| 1111 1101 | 253 | −2 |
| 1000 0001 | 129 | −126 |
| 1000 0000 | 128 | −127 |
Обратный код из двоичного числа представляет собой значение , полученное путем инвертирования всех бит в двоичном представлении числа (свапирования 0 и 1). Эта математическая операция в первую очередь представляет интерес для информатики , где она оказывает различное влияние в зависимости от того, как конкретный компьютер представляет числа.
Система дополнения до единиц или арифметика дополнения единиц - это система, в которой отрицательные числа представлены инверсией двоичных представлений их соответствующих положительных чисел. В такой системе число инвертируется (преобразуется из положительного в отрицательное или наоборот) путем вычисления его дополнения до единиц. N-битовая система счисления с дополнительным кодом может представлять только целые числа в диапазоне от - (2 N − 1 −1) до 2 N − 1 −1, в то время как дополнение до двух может выражать от −2 N − 1 до 2 N − 1 −1. Это одно из трех распространенных представлений отрицательных целых чисел в микропроцессорах , наряду с дополнением до двух и величиной знака .
Комплемент бинарная система счисления характеризуются битовым дополнением любого целого числа , являющееся арифметическим отрицательное значения. То есть инвертирование всех битов числа (логического дополнения) дает тот же результат, что и вычитание значения из 0.
Многие ранние компьютеры, включая UNIVAC 1101 , CDC 160 , CDC 6600 , LINC , PDP-1 и UNIVAC 1107 , использовали арифметику с дополнением до единиц. Преемники CDC 6600 продолжали использовать арифметику с дополнением до двух до конца 1980-х годов, и потомки UNIVAC 1107 (серии UNIVAC 1100/2200 ) все еще используют, но большинство современных компьютеров используют дополнение до двух .
Представление числа
Положительные числа - это та же простая двоичная система, которая используется для дополнения до двух и для знаковой величины. Отрицательные значения - это битовое дополнение к соответствующему положительному значению. Наибольшее положительное значение характеризуется тем, что знаковый (старший) бит выключен (0), а все остальные биты включены (1). Наименьшее отрицательное значение характеризуется тем, что знаковый бит равен 1, а все остальные биты равны 0. В таблице ниже показаны все возможные значения в 4-битной системе от -7 до +7.
+ − 0 0000 1111 — Note that both +0 and −0 return TRUE when tested for zero 1 0001 1110 — and FALSE when tested for non-zero. 2 0010 1101 3 0011 1100 4 0100 1011 5 0101 1010 6 0110 1001 7 0111 1000
Основы
Сложить два значения просто. Просто выровняйте значения по младшему значащему биту и сложите, передав любой перенос на бит, оставшийся на одну позицию слева. Если перенос продолжается за конец слова, говорят, что он «обернут», это состояние называется « переносом в конце ». Когда это происходит, бит необходимо добавить обратно в самый правый бит. Это явление не встречается в арифметике с дополнительным двумя числами.
0001 0110 22 + 0000 0011 3 =========== ==== 0001 1001 25
Вычитание аналогично, за исключением того, что заимствования, а не перенос, распространяются влево. Если заимствование выходит за пределы слова, считается, что оно «обернуто», и это называется « непрерывным заимствованием ». Когда это происходит, бит необходимо вычесть из самого правого бита. Это явление не встречается в арифметике с дополнительным двумя числами.
0000 0110 6 − 0001 0011 19 =========== ==== 1 1111 0011 −12 —An end-around borrow is produced, and the sign bit of the intermediate result is 1. − 0000 0001 1 —Subtract the end-around borrow from the result. =========== ==== 1111 0010 −13 —The correct result (6 − 19 = -13)
Легко продемонстрировать, что битовое дополнение положительного значения является отрицательной величиной положительного значения. Вычисление 19 + 3 дает тот же результат, что и 19 - (−3).
Складываем 3 к 19.
0001 0011 19 + 0000 0011 3 =========== ==== 0001 0110 22
Вычтем −3 из 19.
0001 0011 19 − 1111 1100 −3 =========== ==== 1 0001 0111 23 —An end-around borrow is produced. − 0000 0001 1 —Subtract the end-around borrow from the result. =========== ==== 0001 0110 22 —The correct result (19 − (−3) = 22).
Отрицательный ноль
Отрицательный ноль - это условие, при котором все биты в слове со знаком равны 1. Это соответствует правилам дополнения единиц, согласно которым значение является отрицательным, когда крайний левый бит равен 1, и что отрицательное число является битовым дополнением величины числа. Значение также ведет себя как ноль при вычислении. Добавление или вычитание отрицательного нуля к / из другого значения дает исходное значение.
Добавление отрицательного нуля:
0001 0110 22 + 1111 1111 −0 =========== ==== 1 0001 0101 21 An end-around carry is produced. + 0000 0001 1 =========== ==== 0001 0110 22 The correct result (22 + (−0) = 22)
Вычитая отрицательный ноль:
0001 0110 22 − 1111 1111 −0 =========== ==== 1 0001 0111 23 An end-around borrow is produced. − 0000 0001 1 =========== ==== 0001 0110 22 The correct result (22 − (−0) = 22)
Отрицательный ноль легко получить в сумматоре с дополнением до единицы. Просто сложите положительное и отрицательное одинаковой величины.
0001 0110 22 + 1110 1001 −22 =========== ==== 1111 1111 −0 Negative zero.
Хотя математика всегда дает правильные результаты, побочным эффектом отрицательного нуля является то, что программное обеспечение должно проверять отрицательный ноль.
Избегайте отрицательного нуля
Создание отрицательного нуля становится несложным, если сложение достигается с помощью дополняющего вычитателя. Первый операнд передается в вычитание без изменений, второй операнд дополняется, и вычитание дает правильный результат, избегая отрицательного нуля. В предыдущем примере добавлено 22 и -22 и получено -0.
0001 0110 22 0001 0110 22 1110 1001 −22 1110 1001 −22 + 1110 1001 −22 − 0001 0110 22 + 0001 0110 22 − 1110 1001 −22 =========== ==== but =========== ==== likewise, =========== === but =========== === 1111 1111 −0 0000 0000 0 1111 1111 −0 0000 0000 0
«Угловые случаи» возникают, когда один или оба операнда равны нулю и / или отрицательному нулю.
0001 0010 18 0001 0010 18
− 0000 0000 0 − 1111 1111 −0
=========== ==== =========== ====
0001 0010 18 1 0001 0011 19
− 0000 0001 1
=========== ====
0001 0010 18
Вычитание +0 тривиально (как показано выше). Если второй операнд отрицательный ноль, он инвертируется, и результатом является исходное значение первого операнда. Вычитание −0 также тривиально. Результатом может быть только 1 из двух случаев. В случае 1 операнд 1 равен -0, поэтому результат получается простым вычитанием 1 из 1 в каждой битовой позиции. В случае 2 вычитание сгенерирует значение, которое на 1 больше, чем операнд 1, и заимствование в конце . Завершение заимствования генерирует то же значение, что и операнд 1.
В следующем примере показано, что происходит, когда оба операнда равны нулю плюс или минус:
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0
+ 0000 0000 0 + 1111 1111 −0 + 0000 0000 0 + 1111 1111 −0
=========== ==== =========== ==== =========== ==== =========== ====
0000 0000 0 1111 1111 −0 1111 1111 −0 1 1111 1110 −1
+ 0000 0001 1
==================
1111 1111 −0
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0 − 1111 1111 −0 − 0000 0000 0 − 1111 1111 −0 − 0000 0000 0 =========== ==== =========== ==== =========== ==== =========== ==== 1 0000 0001 1 0000 0000 0 0000 0000 0 1111 1111 −0 − 0000 0001 1 =========== ==== 0000 0000 0
Этот пример показывает, что из 4 возможных условий при добавлении только ± 0 сумматор даст -0 в трех из них. Дополнительный вычитатель даст -0 только тогда, когда оба операнда равны -0.
Смотрите также
Рекомендации
- Дональд Кнут : Искусство компьютерного программирования , том 2: получисловые алгоритмы, глава 4.1