Что такое «Дополнение 2»?

Question

Я учусь на курсе по компьютерным системам и борюсь , частично, с Two's Complement . Я хочу понять это, но все, что я прочитал, не принесло мне картину. Я прочитал статью в Википедии и другие статьи, включая мой учебник .

Следовательно, я хотел бы начать этот пост community wiki , чтобы определить, что такое дополнение Two, как его использовать и как оно может влиять на числа во время операций, таких как приведение (от подписи до неподписания и наоборот), побитовые операции и операции сдвига битов.

Я надеюсь на ясное и краткое определение , которое легко понять программисту.

Answer 1

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

Чтобы понять, нужно думать о числах в двоичном виде.

Это в основном говорит,

• для нуля, используйте все 0.
• для положительных целых чисел, начните отсчет с максимумом 2 ^{(количество битов - 1)} -1.
• для отрицательных целых чисел сделайте то же самое, но поменяйте местами 0 и 1 (поэтому вместо того, чтобы начинать с 0000, начните с 1111 - это часть «дополнения»).

Давайте попробуем это с мини-байтом в 4 бита (назовем это клев - 1/2 байта).

• 0000 - ноль
• 0001 - один
• 0010 - два
• 0011 - три
• 0100 до 0111 - от четырех до семи

Это так далеко, как мы можем пойти в позитивах. 2 ³ -1 = 7.

Для негативов:

• 1111 - отрицательный
• 1110 - два отрицательных
• 1101 - отрицательная тройка
• 1100 до 1000 - от минус четырех до минус восьми

Обратите внимание, что вы получаете одно дополнительное значение для негативов (1000 = -8), которое вы не получаете для позитивов. Это потому, что 0000 используется для нуля. Это можно рассматривать как Номер строки компьютеров.

Различение положительных и отрицательных чисел

При этом первый бит получает роль «знакового» бита, поскольку его можно использовать для различения положительных и отрицательных десятичных значений. Если старший значащий бит 1, то двоичный код можно назвать отрицательным, а если самый старший бит (самый левый) равен 0, можно сказать, что десятичное значение положительно.

"Комплимент" отрицательные числа просто переворачивают бит знака, а затем отсчитывают от 0. Но этот подход должен иметь дело с интерпретацией 1000 как "отрицательный ноль", что вводит в заблуждение. Обычно вам приходится беспокоиться об этом только при работе рядом с оборудованием.

Answer 2

Интересно, можно ли объяснить это лучше, чем статья в Википедии?

Основная проблема, которую вы пытаетесь решить с помощью представления дополнения до двух, - это проблема хранения отрицательных целых чисел.

Сначала рассмотрим целое число без знака, хранящееся в 4 битах. Вы можете иметь следующее

0000 = 0
0001 = 1
0010 = 2
...
1111 = 15

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

Величина знака и избыточное обозначение

Для хранения отрицательных чисел вы можете попробовать несколько вещей. Во-первых, вы можете использовать обозначение величины знака, которое назначает первый бит как знаковый бит для представления +/- и оставшиеся биты для представления величины. Таким образом, снова используя 4 бита и предполагая, что 1 означает - и 0 означает +, тогда вы получите

0000 = +0
0001 = +1
0010 = +2
...
1000 = -0
1001 = -1
1111 = -7

Итак, вы видите проблему там? У нас есть положительные и отрицательные 0. Большая проблема сложения и вычитания двоичных чисел. Схемы сложения и вычитания с использованием величины знака будут очень сложными.

Что такое

0010
1001 +
----

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

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

Преобразование десятичного числа в дополнение к двум

1. Преобразование числа в двоичное (пока игнорируйте знак) например 5 - 0101, а -5 - 0101

2. Если число является положительным числом, то все готово. например 5 - это 0101 в двоичном виде с использованием двойного обозначения дополнения.

3. Если число отрицательное, то

   3.1 найти дополнение (инвертировать 0 и 1) например -5 это 0101, поэтому поиск дополнения составляет 1010

   3.2 Добавьте 1 к дополнению 1010 + 1 = 1011. Следовательно, -5 в дополнении к двум - это 1011.

Так что, если вы хотите сделать 2 + (-3) в двоичном формате? 2 + (-3) равно -1. Что бы вы сделали, если бы вы использовали величину знака для добавления этих чисел? 0010 + 1101 =?

Используя два дополнения, подумайте, насколько легко это будет.

 2  =  0010
 -3 =  1101 +
 -------------
 -1 =  1111

Преобразование дополнения двух в десятичное число

Преобразование 1111 в десятичное число:

1. Число начинается с 1, поэтому оно отрицательное, поэтому мы находим дополнение к 1111, что равно 0000.

2. Добавьте 1 к 0000, и мы получим 0001.

3. Преобразование 0001 в десятичное число, равное 1.

4. Применить знак = -1.

Тад!

Answer 3

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

Вспомните, как это работает для десятичной дроби:
2345
- способ записи
2 & times; 10 ³ + 3 & times; 10 ² + 4 & times; 10 ¹ + 5 & times; 10 ⁰ .

Точно так же двоичный файл - это способ записи чисел, использующий только 0 и 1 , следуя той же общей идее, но заменяя эти 10 выше на 2. Затем в двоичном виде
1111
- это способ записи
1 & times; 2 ³ + 1 & times; 2 ² + 1 & times; 2 ¹ + 1 & times; 2 ⁰
, и если вы решите это, получится равным 15 (основание 10). Это потому, что это
8 + 4 + 2 + 1 = 15.

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

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

К счастью, компьютеры не представляют бесконечности. Числа ограничены определенной длиной (или шириной, если вы предпочитаете). Итак, давайте вернемся к положительным двоичным числам, но с определенным размером. Я буду использовать 8 цифр («бит») для этих примеров. Таким образом, наше двоичное число действительно будет
00001111
или
0 & times; 2 ⁷ + 0 & times; 2 ⁶ + 0 & times; 2 ⁵ + 0 & times; 2 ⁴ + 1 & times; 2 ³ + 1 & times; 2 ² + 1 & times; 2 ¹ + 1 & times; 2 ⁰

Чтобы сформировать отрицание дополнения 2, мы сначала добавляем все (двоичные) цифры к форме
11110000
и добавляем 1 к форме
11110001
но как нам понять, что значит -15?

Ответ заключается в том, что мы меняем значение старшего бита (самого левого). Этот бит будет 1 для всех отрицательных чисел. Изменение будет состоять в том, чтобы изменить знак своего вклада в значение числа, в котором он появляется. Итак, теперь наш 11110001 понимается как
- 1 & times; 2 ⁷ + 1 & times; 2 ⁶ + 1 & times; 2 ⁵ + 1 & times; 2 ⁴ + 0 & times; 2 ³ + 0 & times; 2 ² + 0 & times; 2 ¹ + 1 & times; 2 ⁰
Заметили, что "-" перед этим выражением? Это означает, что знаковый бит имеет вес -2 ⁷ , то есть -128 (основание 10). Все остальные позиции сохраняют тот же вес, что и в двоичных числах без знака.

Вычисление нашего -15, это
-128 + 64 + 32 + 16 + 1
Попробуйте на своем калькуляторе. это -15.

Из трех основных способов, с помощью которых я видел отрицательные числа, представленные в компьютерах, дополнение 2 выигрывает для удобства при общем использовании. Это странно, хотя. Поскольку это двоичный код, должно быть четное количество возможных битовых комбинаций. Каждое положительное число может быть связано с его отрицательным, но есть только один ноль. Отрицание нуля дает вам ноль. Итак, есть еще одна комбинация: число с 1 в знаковом бите и 0 повсюду. Соответствующее положительное число не будет соответствовать количеству используемых битов.

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

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

Answer 4

Дополнение

2 очень полезно для нахождения значения двоичного файла, однако я подумал о гораздо более кратком способе решения такой проблемы (никто не видел, чтобы кто-нибудь опубликовал его):

возьмите двоичный код, например: 1101, который [при условии, что пробел "1" является знаком] равен -3 .

используя дополнение 2, мы сделаем это ... перевернем 1101 на 0010 ... добавим 0001 + 0010 ===>, получим 0011. 0011 в положительном двоичном = 3. поэтому 1101 = -3 !

Что я понял:

вместо того, чтобы все переворачивать и добавлять, вы можете просто сделать основной метод решения для положительного двоичного кода (скажем, 0101): (2 ³ * 0) + (2 ² * 1) + (2 ¹ * 0) + (2 ⁰ * 1) = 5.

Сделайте то же самое с негативом! (С небольшим поворотом)

взять 1101, например:

для первого числа вместо 2 ³ * 1 = 8 , do - (2 ³ * 1) = -8 .

затем продолжите как обычно, выполнив -8 + (2 ² * 1) + (2 ¹ * 0) + (2 ⁰ * 1) = -3

Answer 5

Представьте, что у вас есть конечное число бит / триц / цифр / что угодно. Вы определяете 0 как все цифры, равные 0, и, естественно, рассчитываете вверх:

00
01
02
..

В конце концов вы переполнитесь.

98
99
00

Мы имеем две цифры и можем представлять все числа от 0 до 100. Все эти числа положительные! Предположим, мы тоже хотим представлять отрицательные числа?

То, что у нас действительно есть, это цикл. Число до 2 равно 1. Число до 1 равно 0. Число до 0 равно ... 99 .

Итак, для простоты предположим, что любое число свыше 50 является отрицательным. «0» - «49» означают от 0 до 49. «99» - это -1, «98» - это -2, ... «50» - это -50.

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

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

Answer 6

Два дополнения обнаруживаются путем добавления одного к 1-му дополнению данного числа. Допустим, нам нужно найти два дополнения 10101, а затем найти его дополнение, то есть 01010 добавить 1 к этому результату, то есть 01010+1=01011, что является окончательным ответом.

Answer 7

Позволяет получить ответ 10 - 12 в двоичном виде, используя 8 бит: То, что мы действительно сделаем, это 10 + (-12)

Нам нужно получить комплимент 12, чтобы вычесть его из 10. 12 в двоичном виде - 00001100. 10 в двоичном виде - 00001010.

Чтобы получить комплимент 12, просто поменяйте местами все биты и добавьте 1. 12 в двоичном коде наоборот 11110011. Это также обратный код (дополнение). Теперь нам нужно добавить один, который сейчас 11110100.

Итак, 11110100 - это комплимент 12! Легко, когда ты так думаешь.

Теперь вы можете решить вышеуказанный вопрос 10 - 12 в двоичном виде.

00001010
11110100
-----------------
11111110  

Answer 8

Глядя на систему дополнения двоих с математической точки зрения, это действительно имеет смысл. Идея состоит в том, чтобы в дополнение к десятке «изолировать» разницу.

Пример: 63 - 24 = х

Мы добавляем дополнение 24, которое действительно просто (100 - 24). Поэтому на самом деле все, что мы делаем, это добавляем 100 по обе стороны уравнения.

Теперь уравнение: 100 + 63 - 24 = x + 100, поэтому мы убираем 100 (или 10, или 1000, или что-то еще).

В связи с неудобной ситуацией необходимости вычитать одно число из длинной цепочки нулей, мы используем систему «уменьшенного дополнения к основанию», в десятичной системе - дополнение к девяти.

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

Пример: 99999 - 03275 = 96724

Именно по этой причине после дополнения девяти мы добавляем 1. Как вы, наверное, знаете из математики детства, 9 превращается в 10 путем «кражи» 1. Так что в основном это всего лишь десять дополнений, которые берут 1 из разницы.

В двоичном коде два дополняются до десятого, а одно - до девяти. Основное отличие состоит в том, что вместо того, чтобы пытаться выделить разницу степенями десяти (прибавляя в уравнении 10, 100 и т. Д.), Мы пытаемся выделить разницу степенями два.

Именно по этой причине мы инвертируем биты. Точно так же, как наш миньенд представляет собой цепочку девяток в десятичной системе счисления, так и наш миньенд представляет собой цепочку единиц в двоичном виде.

Пример: 111111 - 101001 = 010110

Поскольку цепочки единиц на 1 ниже милой степени двойки, они «крадут» 1 из разницы, как девятки в десятичной дроби.

Когда мы используем отрицательные двоичные числа, мы на самом деле просто говорим:

0000 - 0101 = x

1111 - 0101 = 1010

1111 + 0000 - 0101 = x + 1111

Чтобы «изолировать» x, нам нужно добавить 1, потому что 1111 - это одно из 10000, и мы удаляем ведущий 1, потому что мы только добавили его к исходной разнице.

1111 + 1 + 0000 - 0101 = x + 1111 + 1

10000 + 0000 - 0101 = х + 10000

Просто удалите 10000 с обеих сторон, чтобы получить х, это базовая алгебра.

Answer 9

Многие ответы до сих пор хорошо объясняют, почему дополнение 2 используется для представления отрицательного числа, но не говорят нам, что такое число дополнения до двух, в частности, не то, почему добавляется «1», а фактически часто добавляется в неправильном виде. способ.

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

Дополнение радиуса n-значного числа x в основании b, по определению, b ^ n-x. В двоичном 4 представляет 100, который имеет 3 цифры (n = 3) и основание 2 (b = 2). Таким образом, его радикальное дополнение: b ^ n-x = 2 ^ 3-4 = 8-4 = 4 (или 100 в двоичном виде).

Тем не менее, в двоичном коде получение дополнения радиуса не так просто, как получение его уменьшенного дополнения радика, которое определяется как (b ^ n-1) -y, всего на 1 меньше, чем у дополнения радиуса. Чтобы получить уменьшенное дополнение к основанию, просто переверните все цифры.

100 -> 011 (уменьшенное (свое) радикальное дополнение)

Чтобы получить основание (два), мы просто добавляем 1, как определено определение.

011 +1 -> 100 (дополнение до двух).

Теперь, с этим новым пониманием, давайте рассмотрим пример, приведенный Винсент Рамдани (см. Второй ответ выше)

/ * начало Винсента

Преобразование 1111 в десятичное число:

Число начинается с 1, поэтому оно отрицательное, поэтому мы находим дополнение к 1111, что равно 0000. Добавьте 1 к 0000, и мы получим 0001. Преобразуйте 0001 в десятичное число, равное 1. Примените знак = -1. Тада!

конец Винсента * /

Следует понимать как

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

дополняют два x: 1111 дополнение к х: 1111-1 -> 1110; х = 0001, (перевернуть все цифры)

применить знак -, а ответ = -x = -1.

Answer 10

Я прочитал фантастическое объяснение на Reddit от jng, используя одометр в качестве аналогии.

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

Представьте себе одометр автомобиля, он катится на (скажем) 99999. Если вы с шагом 00000 вы получите 00001. Если вы уменьшите 00000, вы получите 99999 (из-за откатывания). Если вы добавите один обратно в 99999, он возвращается к 00000. Поэтому полезно решить, что 99999 представляет -1. Также очень полезно решить, что 99998 представляет -2 и так далее. У тебя есть чтобы остановиться где-то, а также по договоренности, верхняя половина чисел считаются отрицательными (50000-99999), а нижняя половина - положительной просто постоять за себя (00000-49999). В результате верхняя цифра 5-9 означает, что представленное число отрицательно, а 0-4 означает, что представленное является положительным - точно так же, как верхний бит представляющий знак в двоичном числе дополнения до двух.

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