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

Question

Я до сих пор не нашел причину, по которой наименьшее отрицательное число со знаком не имеет эквивалентного положительного числа со знаком? Я имею в виду в трехзначном двоичном числе для простоты 100 это -4? но у нас не может быть положительной 4 в подписанном формате, потому что мы не можем. Это переполняет. Итак, как мы узнаем, что дополнение 1000 к двум - это -4 1000, 0000 - -128 и так далее? У нас нет оригинального положительного числа

Answer 1

Один из способов думать об этом заключается в том, что подписанный формат дополнения до двух работает, присваивая каждому биту степень двойки, а затем переворачивая знак последней степени двух.Например, давайте посмотрим на -4, который представлен как 100. Это означает, что значение равно

-1 x 2^2 + 0 x 2^1 + 0 x 2^0

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

 1 x 2^2 - 0 x 2^1 - 0 x 2^0

Обратите внимание, что это значение равно

 1 x 2^2 + 0 x 2^1 + 0 x 2^0

Другими словами, нормальное двоичное представление этого значения равно 100. Однако у нас возникли проблемы, посколькумы используем представление дополнения со знаком два, что означает, что мы специально зарезервировали бит 4 как бит знака.Следовательно, когда мы пытаемся интерпретировать битовую комбинацию 100 как знаковое, трехразрядное значение дополнения до двух, оно возвращается идентично тому, с чего мы начали.Здесь больно нехватка битов.

В более общем смысле, учитывая n битов, из которых первый является знаковым битом в представлении дополнения до двух, попытка вычислить -1000 ... 00 вернет то же самоезначение, потому что бит, необходимый для хранения большого положительного значения, имеет специальное значение, присвоенное ему.

Так зачем вообще это делать?Причина этого заключается в том, что, если у вас есть только n битов, вы не можете сохранить значения от -2 ^{n - 1} до 2 ^{n - 1} , поскольку существует 2 ^{n *Здесь 1019 * + 1 разных чисел и только 2 ^ n разных битовых комбинаций.Исключение наибольшего положительного числа, таким образом, позволяет хранить все различные числа в указанном битовом массиве.}

Но почему отбрасывается высокое значение, а не низкое значение?Это для того, чтобы сохранить двоичную совместимость с целыми числами без знака.В целых числах без знака значения от 0 до 2 ^n-1 - 1 все кодируются с использованием стандартного представления base-two.Следовательно, чтобы целые числа без знака и со знаком были согласованы вообще, целые числа без знака сконструированы таким образом, чтобы они были побитовым эквивалентом первых 2 ^{n - 1} целых чисел без знака, которые варьируются от 0 до 2 ^{n - 1} - 1 включительно.После этого беззнаковые значения нуждаются в старшем значащем бите для кодирования чисел, но знаковые значения используют его как знаковый бит.

Надеюсь, это поможет!

Answer 2

-INT_MIN - это целочисленное переполнение и неопределенное поведение в C.

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

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

Answer 3

Альтернатива дополнения до двух имеет такое свойство, оно известно как дополнение до .
В форме дополнения самое низкое возможное значение также имеет допустимую положительную форму.

---

Дополнение работает, просто инвертируя все биты в самом числе.
Например, мы знаем, что 0110 == 6 и в дополнение 1001 == -6.Используя одно дополнение, мы имеем столько же положительных чисел, сколько и отрицательных.

Но как насчет представления битов 1111?Просто взглянув на это, мы можем сказать, что это «отрицательная» форма нуля (0000 = 0; 1111 = -0), но такое число не имеет никакого смысла и несколько расточительно.

Вместо этого мы используем двадополнение, которое похоже на дополнение, но после инвертирования битов мы добавляем его.Так что, если мы знаем, что 0110 = 6, то дополнение к одному - 1001, а дополнение к двум - 1001 + 1 == 1010.Используя дополнение к двум, у нас нет «отрицательного нуля», потому что это вызывает переполнение.

Другой взгляд на это: «если установлен старший бит, то число отрицательное».Это означает, что положительный диапазон равен [0 .. 2^(bits - 1)], а отрицательный диапазон - это все остальное.Количество положительных чисел такое же, как и отрицательных, но, поскольку (в этом формате) ноль считается положительным, отрицательный диапазон смещается на единицу до [-1 .. (neg) 2^(bits - 1)].

---

Допустим, мыимеет дело с 3-битным числом со знаком в дополнении до двух.Это даст нам следующую таблицу:

BITS  VALUE
000       0
001       1
010       2
011       3

100      -4
101      -3
110      -2
111      -1

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

Answer 4

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

B. Мы хотим, чтобы каждое число, начинающееся с 1, было отрицательным, а каждое число, начинающееся с 0, было отрицательным. (не наоборот, потому что мы хотим, чтобы одно и то же представляло собой положительное и ноль в знаковых и незапятнанных. Из-за этого, 0 - это половина положительных, поэтому их на одно место меньше.

Answer 5

Отсутствует цифра 0.В математическом смысле 0 не является ни положительным, ни отрицательным.Но в двоичном смысле, поскольку 0 не имеет отрицательного бита, он считается положительным.Другими словами, если вы хотите от -128 до 128, не может быть 0.

Answer 6

Потому что вы должны считать 0. Целочисленный диапазон [-4, -1] (или, что эквивалентно -4, -3, -2 и -1) содержит 4 числа и остальную часть диапазона [0,3](или, что эквивалентно 0, 1, 2 и 3) содержит 4 числа, всего 8, а 3-значные двоичные числа имеют 2 в степени 3 (= 8) возможных комбинаций.

Думайте об этом так.Любой целочисленный диапазон вида [-n, + n] обязательно имеет нечетный размер (2 * n + 1 целое число).Какое бы целочисленное двоичное представление вы не использовали, оно будет иметь разное количество отрицательных и положительных чисел, потому что число комбинаций всегда четное (степени 2).

Answer 7

Итак, как мы узнаем, что два дополнения 1000 это -4 1000 0000 это -128 и так далее? У нас нет оригинального положительного числа

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

Процесс поиска дополнения к двум отрицательным числам:

Начните с нормального, отличного от двух, дополнительного представления абсолютного значения числа, которое будет представлено. Поэтому для -4 возьмем представление дополнения к не-двум | -4 |, 100.

Отразить все биты: 100 -> 011 (или ... 11111011, причем те, которые продолжаются до бесконечности влево).

Добавить единицу: 011 -> 100 (или ... 11111100)

Теперь усекаем количество используемых вами битов (это исключает бит переноса или бесконечную строку из 1 с). В результате 100 является 3-битным представлением дополнения до -4.

Чтобы пойти другим путем, возьмите двоичное представление дополнения (100), переверните биты (011) и добавьте одно (100), теперь у вас есть представление дополнения к не-двум | -4 |. 1 * 2 ^ 2 + 0 * 2 ^ 1 + 0 * 2 ^ 0 = 4. Поэтому мы знаем, что представление, с которого мы начали, 100, является 3-битным представлением дополнения до двух -4.