Единицы дополняют - Ones complement - Wikipedia
 | Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. (Январь 2014) (Узнайте, как и когда удалить этот шаблон сообщения) |
| Биты | Без подписи ценить | Единицы дополнять ценить |
|---|---|---|
| 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). Дополнение к числу единиц затем ведет себя как отрицательное значение исходного числа в некоторых арифметических операциях. С точностью до константы (−1) дополнение до единиц ведет себя как отрицательное значение исходного числа с двоичное сложение. Однако в отличие от два дополнения, эти числа не получили широкого распространения из-за таких проблем, как смещение -1, отрицание нуля приводит к отчетливому отрицательный ноль битовая комбинация, меньшая простота с арифметикой заимствование, так далее.
А система дополнения или же арифметика с дополнением до единиц это система, в которой отрицательные числа представлены инверсией двоичных представлений соответствующих им положительных чисел. В такой системе число инвертируется (преобразуется из положительного в отрицательное или наоборот) путем вычисления его дополнения до единиц. N-битная система счисления с дополнительным кодом может представлять только целые числа в диапазоне - (2N − 1−1) до 2N − 1−1, а два дополнения может выразить −2N − 1 до 2N − 1−1.
В двоичное дополнение до единиц система счисления характеризуется битовое дополнение любого целочисленного значения, являющегося арифметическим отрицательным значением. То есть инвертирование всех битов числа (логического дополнения) дает тот же результат, что и вычитание значения из 0.
Многие ранние компьютеры, в том числе 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 - Обратите внимание, что и +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 —An конечный заем создается, а знаковый бит промежуточного результата равен 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 —An конечный заем - 0000 0001 1 - Вычтите из результата конечное заимствование. =========== ==== 0001 0110 22 - Правильный результат (19 - (−3) = 22) .
Отрицательный ноль
Отрицательный ноль - это условие, при котором все биты в слове со знаком равны 1. Это соответствует правилам дополнения единиц, согласно которым значение является отрицательным, когда крайний левый бит равен 1, и что отрицательное число является битовым дополнением величины числа. При вычислении значение также ведет себя как ноль. Добавление или вычитание отрицательного нуля к / из другого значения дает исходное значение.
Добавление отрицательного нуля:
0001 0110 22+ 1111 1111 −0 =========== ==== 1 0001 0101 21 An бесконечный перенос создается. + 0000 0001 1 =========== ==== 0001 0110 22 Правильный результат (22 + (−0) = 22)
Вычитая отрицательный ноль:
0001 0110 22−1111 1111 −0 =========== ==== 1 0001 0111 23 An конечный заем - 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 операнд 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