Дополнение единиц
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( январь 2014 г. ) |
| Биты | Беззнаковое значение | Дополнение единиц ценить |
|---|---|---|
| 000 | 0 | 0 |
| 001 | 1 | 1 |
| 010 | 2 | 2 |
| 011 | 3 | 3 |
| 100 | 4 | −3 |
| 101 | 5 | −2 |
| 110 | 6 | −1 |
| 111 | 7 | −0 |
| Биты | Без подписи ценить |
Единицы дополнять ценить |
|---|---|---|
| 0000 0000 | 0 | 0 |
| 0000 0001 | 1 | 1 |
| 0000 0010 | 2 | 2 |
| 0111 1110 | 126 | 126 |
| 0111 1111 | 127 | 127 |
| 1000 0000 | 128 | −127 |
| 1000 0001 | 129 | −126 |
| 1111 1101 | 253 | −2 |
| 1111 1110 | 254 | −1 |
| 1111 1111 | 255 | −0 |
Дополнением единиц до двоичного числа является значение, полученное путем инвертирования (переворачивания) всех битов в двоичном представлении числа. Название «дополнение единиц» [1] относится к тому факту, что такое перевернутое значение, если оно добавлено к исходному, всегда будет давать число «все единицы» (термин « дополнение » относится к таким парам взаимно аддитивных обратных чисел, здесь в отношении основания, отличного от 0). число). Эта математическая операция представляет интерес в первую очередь в информатике , где она имеет различные эффекты в зависимости от того, как конкретный компьютер представляет числа.
Система дополнения до единиц или арифметика с дополнением до единиц - это система, в которой отрицательные числа представлены инверсией двоичных представлений соответствующих им положительных чисел. В такой системе число отрицается (преобразуется из положительного в отрицательное или наоборот) путем вычисления дополнения к нему. N-битная система счисления с дополнением до единиц может представлять только целые числа в диапазоне −(2 Н-1 −1) до 2 Н-1 −1, тогда как дополнение до двух может выражать −2 Н-1 до 2 Н-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. В таблице ниже показаны все возможные значения в четырехбитной системе от -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 равен −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
Этот пример показывает, что из четырех возможных условий при сложении только ±0 сумматор выдаст -0 в трех из них. Дополняющий вычитатель выдаст −0 только тогда, когда первый операнд равен −0, а второй равен 0.
См. также
[ редактировать ]
Ссылки
[ редактировать ]- ^ Кнут, Дональд Э. «4.1. Позиционные системы счисления». Искусство компьютерного программирования, Том 2: Получисловые алгоритмы (3-е изд.).
Внимательные читатели и редакторы должны обратить внимание на положение апострофа в таких терминах, как «дополнение до двух» и «дополнение до единиц»: число, дополняемое до двух, дополняется относительно одинарной степени двойки, а число, дополняемое до единиц, — дополняется относительно длинной последовательности единиц.
- Дональд Кнут : Искусство компьютерного программирования , Том 2: Получисловые алгоритмы , глава 4.1