Арифметика с неподписанными переменными в C

Question

Как может беззнаковый символ принимать значения от -128 до +127? Из того, что я понимаю, самый старший бит используется для представления знака числа, а остальные бит символа используются для представления величины числа. Теперь наибольшая возможная величина для 7 бит равна 127, поэтому диапазон не должен быть от -127 до +127? Как может -128 быть результатом?

Во-вторых, то, что логика битового уровня за следующее поведение

#include <stdio.h> 

int main() 
{ 
    signed char x = 127; 
    x += 1; 
    printf("%i", x); 
} 

Выход:

-128 

Как можно видеть, x становится -128, но почему? Какова арифметика этого поведения?

Answer 1

Это работает на основе чего-то, называемого Two's Complement. Идея здесь заключается в том, что с учетом двоичного числа это два дополнения - это одно дополнение (flip all bits) плюс одно. Мы можем увидеть простой пример, давайте найдем два дополнения от 13, которые мы можем написать как 0b01101. 01101 (flip) -> 10010 (+1) --> 10011

Теперь, хотя, если мы интерпретировали, что как двоичное число, как обычно, мы читали 19 в десятичной системе счисления, мы должны знать, что число записывается в Дополнении Two для того, чтобы полностью изменить процедуру и прийти к предыдущему номеру 13. Итак, из этого мы видим, что мы представили такие вещи, что +13 = 01101 и -13 = 10011, заметим, что положительное число начинается с 0 и является симметричным с 1. Это будет константой при использовании этого представления, положительные числа всегда начинаются с 0, а отрицательные - с 1. Что-то еще, что стоит отметить, это то, что я префикс 0 в свое первоначальное представление 13, которое понадобится для правильного представления его двух дополнений. Вы можете попробовать пройти один и тот же пример, не делая этого и проверяя его необходимость.

Теперь давайте рассмотрим несколько значений, представленных как это,

╔══════╦════════════════╦════════════════════════╗ 
║ Bits ║ Unsigned Value ║ Two's Complement Value ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 011 ║ 3    ║ 3      ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 010 ║ 2    ║ 2      ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 001 ║ 1    ║ 1      ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 000 ║ 0    ║ 0      ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 111 ║ 7    ║ -1      ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 110 ║ 6    ║ -2      ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 101 ║ 5    ║ -3      ║ 
╠══════╬════════════════╬════════════════════════╣ 
║ 100 ║ 4    ║ -4      ║ 
╚══════╩════════════════╩════════════════════════╝ 

Как вы можете видеть, это работает точно так же, как мы уже ранее предполагалось, однако теперь вы можете начать понимать, как «ошибка «вы обнаружили, что случилось. Верхним пределом для 4-битного представления в дополнении 2 является десятичное значение 3. Давайте посмотрим, как мы достигнем -4, просто добавив 1. 3 = 0b011 поэтому 3+1 = 0b100, который, как вы можете видеть из таблицы, соответствует -4 (в отличие от 4) на дополнении Два. Ваш случай был этой точной проблемой, но с большим количеством бит. Подписанное представление, подобное этому, является круглым, поэтому переполнение сверху дает нижнее значение. Давайте посмотрим на вашем случае

127 = 0b01111111 
127 + 1 = 0b10000000 

Как вы можете видеть, что это начинается с 1, поэтому отрицательным (!), А если вы решите дополните двойки вы увидите, что она представляет -128 (как нижняя граница всегда больше верхней границы).

Дано то, что не все аппаратные средства будут реализовывать вещи одинаково, Intel, AMD, ARM и, насколько мне известно, все основные архитектуры для процессоров общего назначения используют дополнение Two в своих ALU, но есть оборудование, которое использует другие методы для реализации подписи целых чисел, поэтому принципиально описанное вами поведение не определено. Еще одна интересная вещь - IEEE's standard for floating point arithmetic, реализует подписанный поплавок exponent bias.

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

Answer 2

В C поведение оператора += определяется эквивалентной комбинацией = и + операторов. Например. ваш x += 1 по определению означает x = x + 1. Поскольку x имеет узкий тип signed char, это повышается до int, прежде чем начнется любая арифметика. Это означает, что подвыражение x + 1 оценивается в домене типа int. После этого результат (типа int) преобразуется обратно в signed char и сохраняется обратно в x.

Таким образом, в вашем случае ваш x += 1 фактически эквивалентно

x = (signed char) ((int) x + 1); 

(int) x + 1 подвыражения не переполнения. Он успешно производит значение 128 типа int. Однако это значение не вписывается в диапазон signed char, что приводит к реализации, определяемому реализацией, когда это значение преобразуется обратно в signed char. На вашей платформе это поведение, определяемое реализацией, дает значение -128 типа signed char.