Почему для чисел со знаком предпочитают два дополнения над знаком и величиной? - PullRequest
186 голосов
/ 14 июля 2009

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

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

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

Ответы [ 18 ]

311 голосов
/ 14 июля 2009

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

Скажем, у вас есть два числа, 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"

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

Есть еще один бонус с хранением целых значений таким образом, и именно тогда вам нужно увеличить ширину регистра, в котором хранится значение. С дополнением до двух, сохранение 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-й бит. Это один крошечный дополнительный шаг в одной из самых фундаментальных и распространенных операций, присутствующих в каждом приложении.

18 голосов
/ 14 июля 2009

Википедия говорит само за себя:

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

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

12 голосов
/ 14 июня 2014

Несмотря на то, что этот вопрос старый, позвольте мне положить мои 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. Таким образом, приведенное выше утверждение становится: Любое n'bit число + его дополнение 2 = 0 что означает 2-е дополнение числа = - (этого числа)

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

8 голосов
/ 14 июля 2009

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

6 голосов
/ 14 июля 2009

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

5 голосов
/ 14 июля 2009

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

Принимая 8-битное значение a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0

Обычная бинарная интерпретация без знака:
2 7 * a 7 + 2 6 * a 6 + 2 5 * a 5 + 2 4 * a 4 + 2 3 * a 3 + 2 2 * a 2 + 2 1 * a 1 + 2 0 * a 0
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

Интерпретация двух дополнений:
-2 7 * a 7 + 2 6 * a 6 + 2 5 * a 5 + 2 4 * a 4 + 2 3 * a 3 + 2 2 * a 2 + 2 1 * a 1 + 2 0 * a 0
11111111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1

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

4 голосов
/ 14 июля 2009

Чтобы расширить на другие ответы:

В двух дополнениях

  • Добавление - это тот же механизм, что и при добавлении простых натуральных чисел.
  • Вычитание тоже не меняется
  • Умножение тоже!

Деление требует другого механизма.

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

3 голосов
/ 14 июля 2009

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

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

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

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

То же самое относится и к вычитанию.

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

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

2 голосов
/ 03 сентября 2015

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

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

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

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

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

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

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

  • char имеют длину 1 байт
  • short длиной 2 байта
  • int и float имеют длину 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 с одинарной точностью

[EDIT] Это сообщение было отредактировано после комментария user4581301. Спасибо, что нашли время отбросить эти несколько полезных строк!

1 голос
/ 15 июля 2009

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

...