Дополнением до единиц двоичного числа является значение, полученное путем инвертирования (переворачивания) всех битов в двоичном представлении числа. Название «дополнение единиц» [1] относится к тому факту, что такое перевернутое значение, если добавить его к исходному, всегда будет давать число «все единицы» (термин « дополнение » относится к таким парам взаимно аддитивных обратных чисел) . , здесь в отношении базового числа, отличного от 0). Эта математическая операция представляет интерес в первую очередь в информатике , где она имеет различные эффекты в зависимости от того, как конкретный компьютер представляет числа.
Система дополнения до единиц или арифметика с дополнением до единиц - это система, в которой отрицательные числа представлены инверсией двоичных представлений соответствующих им положительных чисел. В такой системе число отрицается (преобразуется из положительного в отрицательное или наоборот) путем вычисления дополнения к нему. 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. В таблице ниже показаны все возможные значения в четырехбитной системе от -7 до +7.
+ − 0 0000 1111 — Обратите внимание, что и +0, и -0 возвращают TRUE при проверке на ноль. 1 0001 1110 — и FALSE при проверке на ненулевое значение. 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 — Производится сквозное заимствование, и знаковый бит промежуточного результата равен 1.− 0000 0001 1 — Вычтите из результата заимствование в конце.=========== ==== 1111 0010 −13 — Правильный результат (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 — Производится кольцевой заем .− 0000 0001 1 — Вычтите из результата заимствование в конце.=========== ==== 0001 0110 22 — Правильный результат (19 − (−3) = 22).
Отрицательный ноль — это состояние, при котором все биты в слове со знаком равны 1. Это соответствует правилам дополнения до единиц, согласно которым значение является отрицательным, когда самый левый бит равен 1, и что отрицательное число является битовым дополнением величины числа. Значение также ведет себя как нулевое при вычислении. Добавление или вычитание отрицательного нуля к/из другого значения дает исходное значение.
Добавление отрицательного нуля:
0001 0110 22+ 1111 1111 −0=========== ====1 0001 0101 21 Производится круговой перенос .+ 0000 0001 1=========== ==== 0001 0110 22 Правильный результат (22 + (−0) = 22)
Вычитание отрицательного нуля:
0001 0110 22− 1111 1111 −0=========== ====1 0001 0111 23 Производится сквозное заимствование .− 0000 0001 1=========== ==== 0001 0110 22 Правильный результат (22 − (−0) = 22)
Отрицательный ноль легко получить в сумматоре с дополнением до единиц. Просто сложите положительное и отрицательное одинаковой величины.
0001 0110 22+ 1110 1001 −22=========== ==== 1111 1111 −0 Отрицательный ноль.
Хотя математические вычисления всегда дают правильные результаты, побочным эффектом отрицательного нуля является то, что программное обеспечение должно проверять отрицательный ноль.
Генерация отрицательного нуля становится не проблемой, если сложение достигается с помощью дополняющего вычитателя. Первый операнд передается в операцию вычитания без изменений, второй операнд дополняется, и вычитание генерирует правильный результат, избегая отрицательного нуля. В предыдущем примере были добавлены 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=========== ==== но =========== ==== аналогично, =========== === но == ========= === 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.
Внимательные читатели и редакторы должны обратить внимание на положение апострофа в таких терминах, как «дополнение до двух» и «дополнение до единиц»: число, дополняемое до двух, дополняется относительно одинарной степени двойки, а число, дополняемое до единиц, — дополняется относительно длинной последовательности единиц.
