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

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

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

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

 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 ⁿ + 1 разных чисел здесь и только 2 ^ n различных битовых комбинаций. Таким образом, исключение наибольшего положительного числа позволяет хранить все различные числа в указанном битовом шаблоне.

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

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

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

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

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

Хорошо известный пример оптимизации компилятора:

#define ABS(x) ((x) > 0 ? (x) : -(x)) 

void foo(int x){  
    if (ABS(x) >= 0) {
        // some code
    }
}

большинство современных компиляторов (gcc, icc) с включенными параметрами оптимизации оптимизируют тест, полагаясь на тот факт, что -INT_MIN является неопределенным поведением.

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

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

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

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

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

Потому что вам нужно считать 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 целое число). Какое бы целочисленное двоичное представление вы ни использовали, оно будет иметь разное количество отрицательных и положительных чисел, потому что количество комбинаций всегда четное (степени двойки).

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

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

Процесс поиска двойного дополнения отрицательного числа:

Начните с обычного, не дополняющего два представления абсолютного значения числа, которое нужно представить. Итак, для -4 возьмем не двойное дополнительное представление | -4 |, 100.

Переверните все биты: 100 -> 011 (или ... 11111011 с бесконечным продолжением битов влево).

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

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

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