Дополнение до единиц двоичного числа — это значение, полученное путем инвертирования (переворачивания) всех битов в двоичном представлении числа. Название «дополнение до единиц» [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. В таблице ниже показаны все возможные значения в четырехбитной системе от −7 до +7.
+ − 0 0000 1111 — Обратите внимание, что и +0, и −0 возвращают значение ИСТИНА при проверке на ноль. 1 0001 1110 — и ЛОЖЬ при проверке на ненулевое значение. 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.
Читатели и редакторы, ориентированные на детали, должны обратить внимание на положение апострофа в терминах типа "дополнение до двух" и "дополнение до единиц": число в дополнительном коде дополняется относительно единичной степени числа 2, в то время как число в дополнительном коде дополняется относительно длинной последовательности единиц.
