Почему для чисел со знаком предпочтительнее дополнение "два", а не "знак-величина"?

https://stackoverflow.com/questions/1125304

13-09-2019
|

Вопрос

Мне просто любопытно, есть ли причина, по которой для представления -1 в двоичном формате используется дополнение two:переворачиваем биты и добавляем 1?

-1 представлено 11111111 (дополнением к двум), а не (для меня более интуитивно понятным) 10000001, которое является двоичным 1 с первым битом в качестве отрицательного флага.

Отказ от ответственности:Я не полагаюсь на двоичную арифметику в своей работе!

Решение

Это сделано для того, чтобы сложение не нуждалось в какой-либо специальной логике для работы с отрицательными числами.Проверьте статья в Википедии.

Допустим, у вас есть два числа, 2 и -1.В вашем "интуитивном" способе представления чисел они были бы 0010 и 1001, соответственно (я придерживаюсь 4 бит для размера).Дополняя друг друга, они являются 0010 и 1111.Теперь, допустим, я хочу их добавить.

Дополнение двойки сложение двойки очень простое.Вы добавляете числа обычным образом, и любой бит переноса в конце отбрасывается.Таким образом, они добавляются следующим образом:

  0010
+ 1111
=10001
= 0001 (discard the carry)

0001 равно 1, что является ожидаемым результатом "2+(-1)".

Но в вашем "интуитивном" методе добавление происходит сложнее:

  0010
+ 1001
= 1011

Что равно -3, верно?Простое сложение в этом случае не работает.Вам нужно отметить, что одно из чисел отрицательное, и использовать другой алгоритм, если это так.

Для этого "интуитивного" метода хранения вычитание отличается от сложения операцией, требующей дополнительных проверок чисел, прежде чем их можно будет сложить.Поскольку вы хотите, чтобы самые простые операции (сложение, вычитание и т.д.) выполнялись как можно быстрее, вам необходимо хранить числа таким образом, чтобы вы могли использовать максимально простые алгоритмы.

Кроме того, в "интуитивном" методе хранения есть два нуля:

0000  "zero"
1000  "negative zero"

Которые интуитивно являются одним и тем же числом, но при сохранении имеют два разных значения.Каждому приложению потребуется предпринять дополнительные шаги, чтобы убедиться, что ненулевые значения также не равны отрицательному нулю.

Есть еще один бонус при хранении целых чисел таким образом, и это когда вам нужно увеличить ширину регистра, в котором хранится значение.С дополнением two сохранение 4-разрядного числа в 8-разрядном регистре сводится к повторению его самого значащего бита:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1110 (negative two, in four bits)
11111110 (negative two, in eight bits)

Это просто вопрос того, чтобы посмотреть на знаковый бит меньшего слова и повторять его до тех пор, пока он не увеличит ширину большего слова.

С помощью вашего метода вам нужно было бы очистить существующий бит, что является дополнительной операцией в дополнение к заполнению:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1010 (negative two, in four bits)
10000010 (negative two, in eight bits)

Вам все равно нужно установить эти дополнительные 4 бита в обоих случаях, но в "интуитивном" случае вам также нужно очистить 5-й бит.Это один крошечный дополнительный шаг в одной из самых фундаментальных и распространенных операций, присутствующих в каждом приложении.

Другие советы

Википедия этим все сказано:

Система двойного дополнения имеет преимущество в том, что не требует, чтобы схемы сложения и вычитания проверяли знаки операндов, чтобы определить, следует ли добавлять или вычитать.Это свойство делает систему как более простой в реализации, так и способной легко обрабатывать арифметические вычисления более высокой точности.Кроме того, ноль имеет только одно представление, устраняя тонкости, связанные с отрицательным нулем, который существует в системах с дополнением.

Другими словами, сложение происходит одинаково, независимо от того, является число отрицательным или нет.

Несмотря на то, что этот вопрос устарел, позвольте мне вставить свои 2 цента.

Прежде чем я объясню это, давайте вернемся к основам.дополнение 2' - это дополнение 1 + 1 .Теперь, что такое дополнение 1 и каково его значение в дополнение.

Сумма любого n-битного числа и его дополнения 1 дает вам максимально возможное число, которое может быть представлено этими n битами.Пример:

 0010 (2 in 4 bit system)
+1101 (1's complement of 2)
___________________________
 1111  (the highest number that we can represent by 4 bits)

Теперь, что произойдет, если мы попытаемся добавить еще 1 к результату.Это приведет к переполнению.

Результатом будет 1 0000 который равен 0 ( поскольку мы работаем с 4 - битными числами , (1 слева - это переполнение ) .

Итак ,

Any n-bit number + its 1's complement = max n-bit number
Any n-bit number + its 1'complement + 1 = 0 ( as explained above, overflow will occur as we are adding 1 to max n-bit number)

Затем кто-то решил назвать дополнение 1 + 1 как дополнение 2 'complement.Таким образом, приведенное выше утверждение становится:Любое n-битное число + его дополнение 2 = 0 что означает, что дополнение 2 к числу = - (этого числа)

Все это порождает еще один вопрос : почему мы можем использовать только (n-1) из n битов для представления положительного числа и почему самый левый n-й бит представляет знак (0 в крайнем левом бите означает + пять чисел , а 1 означает -пять чисел ) .например, почему мы используем только первые 31 бит int в java для представления положительного числа, если 32-й бит равен 1 , его a -ve число.

 1100 (lets assume 12 in 4 bit system)
+0100(2's complement of 12)
___________________________

1 0000 (результат равен нулю , при переносе 1 переполнен)

Таким образом, система (n + 2' выполнение n) = 0 , все еще работает.Единственная двусмысленность здесь заключается в том, что дополнение 2 к 12 равно 0100, которое неоднозначно также представляет + 8 , отличное от представления -12 в системе дополнения 2s.

Эта проблема будет решена, если положительные числа всегда будут иметь 0 в самом левом бите.В этом случае их дополнение 2 всегда будет содержать 1 в самом левом бите, и у нас не будет двусмысленности из-за того, что один и тот же набор битов представляет номер дополнения 2, а также число + ve.

Дополнение двух позволяет выполнять сложение и вычитание обычным способом (как вы делали для чисел без знака).Это также предотвращает -0 (отдельный способ представления 0, который не был бы равен 0 при обычном побитовом методе сравнения чисел).

это делается для упрощения сумм и разностей чисел.сумма отрицательного числа и положительного, кодифицированная в дополнениях 2, - это то же самое, что и их суммирование обычным способом.

Обычная реализация операции - "переверните биты и добавьте 1", но есть другой способ ее определения, который, вероятно, делает обоснование более ясным.Дополнение 2 - это форма, которую вы получите, если возьмете обычное представление без знака, где каждый бит управляет следующей степенью 2, и просто сделаете самый значимый член отрицательным.

Принимая 8-битное значение a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀

Обычная двоичная интерпретация без знака является:
2⁷*a₇ + 2⁶*a₆ + 2⁵*a₅ + 2⁴*a₄ + 2³*a₃ + 2²*a₂ + 2¹*a₁ + 2⁰*a₀
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

Дополняющая интерпретация этих двух является:
-2⁷*a₇ + 2⁶*a₆ + 2⁵*a₅ + 2⁴*a₄ + 2³*a₃ + 2²*a₂ + 2¹*a₁ + 2⁰*a₀
11111111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1

Ни один из других битов вообще не меняет значения, и перенос в₇ является "переполнением" и, как ожидается, не будет работать, поэтому практически все арифметические операции работают без изменений (как отмечали другие).Знаковая величина обычно проверяет знаковый бит и использует другую логику.

Дополнение Two позволяет суммировать отрицательные и положительные числа без какой-либо специальной логики.

Если вы попытались добавить 1 и -1, используя свой метод
10000001 (-1)
+00000001 (1)
вы получаете
10000010 (-2)

Вместо этого, используя дополнение two, мы можем добавить

11111111 (-1)
+00000001 (1) вы получаете
00000000 (0)

То же самое верно и для вычитания.

Кроме того, если вы попытаетесь вычесть 4 из 6 (два положительных числа), вы можете 2 дополнить 4 и сложить два вместе 6 + (-4) = 6 - 4 = 2

Это означает, что вычитание и сложение как положительных, так и отрицательных чисел может выполняться одной и той же схемой в процессоре.

Чтобы расширить информацию о других ответах:

В дополнении к двум

Сложение - это тот же механизм, что и сложение простых положительных целых чисел.
Вычитание тоже не меняется
Умножение тоже!

Разделение действительно требует другого механизма.

Все это верно, потому что дополнение two - это просто обычная модульная арифметика, где мы рассматриваем некоторые числа как отрицательные путем вычитания по модулю.

Читая ответы на этот вопрос, я наткнулся на этот комментарий [отредактировано].

дополнение 2 к 0100(4) будет равно 1100.Теперь 1100 равно 12, если я говорю нормально.Итак,, когда я говорю обычный 1100, тогда это 12, но когда я говорю, что 2 дополняют 1100, тогда это -4?Кроме того, в Java, когда сохраняется 1100 (на данный момент предположим, что 4 бита), тогда как определяется, равно ли это + 12 или -4??– хагравал 2 июля в 16:53

На мой взгляд, вопрос, заданный в этом комментарии, довольно интересный, и поэтому я хотел бы прежде всего перефразировать его, а затем предоставить ответ и пример.

ВОПРОС – Как система может установить, как должен интерпретироваться один или несколько соседних байтов?В частности, как система может установить, является ли данная последовательность байтов простым двоичным числом или числом дополнения 2?

ОТВЕТ – Система устанавливает, как интерпретировать последовательность байтов с помощью типов.Типы определяют

сколько байтов нужно учитывать
как эти байты должны быть интерпретированы

ПРИМЕР – Ниже мы предполагаем, что

char's имеют длину 1 байт
short's имеют длину 2 байта
int's и float's имеют длину 4 байта

Пожалуйста, обратите внимание, что эти размеры специфичны для моей системы.Хотя они довольно распространены, они могут отличаться от системы к системе.Если вам интересно, какие они есть в вашей системе, используйте оператор sizeof.

Прежде всего, мы определяем массив, содержащий 4 байта, и инициализируем все из них двоичным числом 10111101, соответствующий шестнадцатеричному числу BD.

// BD(hexadecimal) = 10111101 (binary)
unsigned char   l_Just4Bytes[ 4 ]   =   { 0xBD, 0xBD, 0xBD, 0xBD };

Затем мы считываем содержимое массива, используя разные типы.

`unsigned char` и `signed char`

// 10111101 as a PLAIN BINARY number equals 189
printf( "l_Just4Bytes as unsigned char  -> %hi\n", *( ( unsigned char* )l_Just4Bytes ) );

// 10111101 as a 2'S COMPLEMENT number equals -67
printf( "l_Just4Bytes as signed char    -> %i\n", *( ( signed char* )l_Just4Bytes ) );

`unsigned short` и `short`

// 1011110110111101 as a PLAIN BINARY number equals 48573
printf( "l_Just4Bytes as unsigned short -> %hu\n", *( ( unsigned short* )l_Just4Bytes ) );

// 1011110110111101 as a 2'S COMPLEMENT number equals -16963
printf( "l_Just4Bytes as short          -> %hi\n", *( ( short* )l_Just4Bytes ) );

`unsigned int`, `int` и `float`

// 10111101101111011011110110111101 as a PLAIN BINARY number equals 3183328701
printf( "l_Just4Bytes as unsigned int   -> %u\n", *( ( unsigned int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a 2'S COMPLEMENT number equals -1111638595
printf( "l_Just4Bytes as int            -> %i\n", *( ( int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a IEEE 754 SINGLE-PRECISION number equals -0.092647
printf( "l_Just4Bytes as float          -> %f\n", *( ( float* )l_Just4Bytes ) );

4 байта в оперативной памяти (l_Just4Bytes[ 0..3 ]) всегда остаются точно такими же.Единственное, что меняется, - это то, как мы их интерпретируем.

Снова, мы сообщите системе как интерпретировать их через типы.

Например, выше мы использовали следующие типы для интерпретации содержимого l_Just4Bytes массив

unsigned char:1 байт в обычном двоичном формате
signed char:1 байт в дополнении к 2
unsigned short:2 байта в простой двоичной системе счисления
short:2 байта в дополнении 2
unsigned int:4 байта в простой двоичной системе счисления
int:4 байта в дополнении к 2
float:4 байта в системе счисления одинарной точности IEEE 754

[РЕДАКТИРОВАТЬ] Этот пост был отредактирован после комментария пользователя 4581301.Спасибо, что нашли время написать эти несколько полезных строк!

Вы можете посмотреть, как профессор Джерри Кейн из Стэнфорда объясняет дополнение двух, во второй лекции (объяснение относительно дополнения двух начинается около 13:00) в серии лекций под названием "Парадигмы программирования", доступных для просмотра на YouTube-канале Стэндфорда.Вот ссылка на серию лекций: http://www.youtube.com/view_play_list?p=9D558D49CA734A02.

Дополнение Two используется потому, что его проще реализовать в схемотехнике, а также оно не допускает отрицательного нуля.

Если имеется x битов, дополнение two будет варьироваться от + (2^ x /2+ 1) до -(2^x/2).Дополнение одного будет выполняться от + (2 ^ x / 2) до - (2 ^ x / 2), но допускает отрицательный ноль (0000 равно 1000 в 4-битной системе дополнения 1).

Ну, на самом деле ваше намерение не состоит в том, чтобы обратить вспять все биты вашего двоичного числа.На самом деле это состоит в том, чтобы вычесть каждую свою цифру из 1.Это просто удачное совпадение, что вычитание 1 из 1 приводит к 0, а вычитание 0 из 1 приводит к 1.Таким образом, переворачивание битов эффективно выполняет это вычитание.

Но почему вы находите отличие каждой цифры от 1?Ну, а ты - нет.Ваше фактическое намерение состоит в том, чтобы вычислить отличие данного двоичного числа от другого двоичного числа, которое имеет такое же количество цифр, но содержит только единицы.Например, если ваше число равно 10110001, когда вы переворачиваете все эти биты, вы эффективно вычисляете (11111111 - 10110001).

Это объясняет первый шаг в вычислении Дополнения Two.Теперь давайте включим второй шаг - добавление 1 - также на картинке.

Добавьте 1 к приведенному выше двоичному уравнению:

11111111 - 10110001 + 1

Что ты получаешь?Это:

100000000 - 10110001

Это окончательное уравнение.И, выполняя эти два шага, вы пытаетесь найти это, окончательное различие:двоичное число, вычитаемое из другого двоичного числа с одной дополнительной цифрой и содержащее нули, за исключением самой значимой позиции бита.

Но почему на самом деле мы стремимся к этой разнице?Что ж, с этого момента, я думаю, было бы лучше, если бы вы прочитали Статья в Википедии.

Мы выполняем только операцию сложения как для сложения, так и для вычитания.Мы добавляем второй операнд к первому операнду для сложения.Для вычитания мы добавляем дополнение 2 второго операнда к первому операнду.

При представлении дополнения 2 нам не нужны отдельные цифровые компоненты для вычитания — используются только сумматоры и дополнители.

Стоит отметить, что на некоторых ранних арифмометрах, до появления цифровых компьютеров, вычитание выполнялось путем ввода оператором значений, используя набор условных обозначений разного цвета на каждой клавише (таким образом, каждая клавиша вводила бы девять минус число, подлежащее вычитанию), и нажатие специальной кнопки предполагало бы перенос в вычисление.Таким образом, на шестизначном компьютере, чтобы вычесть 1234 из значения, оператор нажимал клавиши, которые обычно обозначают "998,765", и нажимал кнопку, чтобы добавить это значение плюс один к выполняемому вычислению.Арифметика с дополнением к двум - это просто двоичный эквивалент более ранней арифметики с дополнением к десяти.

Преимуществом выполнения вычитания методом дополнения является сокращение аппаратных средств
сложность.Нет необходимости в разных цифровых схемах для сложения и вычитания.оба сложение и вычитание выполняются только сумматором.

Основное преимущество представления с дополнением к двум, которое здесь еще не упоминалось, заключается в том, что младшие биты суммы, разницы или произведения с дополнением к двум зависят Только на соответствующие биты операндов.Причина, по которой 8-битное значение со знаком для -1 является 11111111 это вычитание Любой целое число , младшие 8 бит которого равны 00000001 из любого другого целого числа , младшие 8 бит которого равны 0000000 выдаст целое число, младшие 8 бит которого равны 11111111.Математически значение -1 было бы бесконечной строкой из единиц, но все значения в диапазоне определенного целочисленного типа будут либо равны всем единицам, либо всем 0 после определенной точки, поэтому компьютерам удобно "расширять со знаком" самый значащий бит числа, как если бы он представлял бесконечное число единиц или 0.

Дополнение к двум - это практически единственное представление со знаком числа, которое хорошо работает при работе с типами, размер которых превышает естественный размер слова двоичной машины, поскольку при выполнении сложения или вычитания код может извлекать наименьшую часть каждого операнда, вычислять наименьшую часть результата и сохранять это, затем загружать следующую часть каждого операнда, вычислять следующую часть результата и сохранять это и т.д.Таким образом, даже процессор, который требует, чтобы все сложения и вычитания выполнялись через один 8-разрядный регистр, может достаточно эффективно обрабатывать 32-разрядные числа со знаком (конечно, медленнее, чем с 32-разрядным регистром, но все же работоспособен).

При использовании любых других подписанных представлений, разрешенных стандартом C, любой бит операндов потенциально может повлиять на каждый бит результата, что делает необходимым либо одновременное хранение всего значения в регистрах, либо выполнение вычислений с дополнительным шагом, который, по крайней мере в некоторых случаях, потребовал бы чтения, изменения и перезаписи каждого фрагмента результата.

Один удовлетворительный ответ на вопрос, почему дополнение Two2 используется для представления отрицательных чисел, а не системы дополнения One, заключается в том, что Система дополнения Two решает проблему множественные представления 0 и необходимость в конец-вокруг-перенос которые существуют в системе дополнения One для представления отрицательных чисел.

Для получения дополнительной информации посетите https://en.wikipedia.org/wiki/Signed_number_representations

Для окончательного переноса Посетите https://en.wikipedia.org/wiki/End-around_carry

потому что производители процессоров ленивы!

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow

Почему для чисел со знаком предпочтительнее дополнение "два", а не "знак-величина"?

unsigned char и signed char

unsigned short и short

unsigned int, int и float

`unsigned char` и `signed char`

`unsigned short` и `short`

`unsigned int`, `int` и `float`