C ++ переполнение влево для отрицательных чисел

Question

Как показано ниже, в коде есть ошибка. При вводе a = -1, b = 1 одна из строк имеет ошибку во время выполнения. Не могли бы вы помочь мне понять, как (a & b) становится INT_MIN?

В моем понимании, -1 представлен как 32-битный двоичный формат 0xFFFFFFFF, а 1 представлен как 32-битный формат 0x00000001, таким образом (-1 & 1) станет 0x00000001. И моя команда python также показывает '0b1' как результат. Почему он сообщает об ошибке INT_MIN?

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;//BUG! left shift of negative value -2147483648
        a = a ^ b;
        b = carry;
    }

    return a;
}

Обновление: правильно ли задан сдвиг вправо для отрицательных чисел? Кажется правильным смещать отрицательные числа вправо, если оно удовлетворяет требованиям, приведенным ниже.

с сайта cppreference.com,

Для неподписанного a и для подписанного a с неотрицательными значениями значение a >> b - целая часть a / 2b. Для отрицательного значения a >> b определяется реализацией (в большинстве реализаций это выполняет арифметическое смещение вправо, так что результат остается отрицательным).

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

Answer 1

Предполагая, что это C или C ++, ваша ошибка заключается в том, что Сдвиг влево отрицательного значения равен неопределенному поведению , а смещение влево значения со знаком, так что оно становится больше, чем MAX_INT, также является неопределенным поведением.

Если вы проверите значения a и b при выполнении этой последовательности, вы получите:

-1 1
-2 2
-4 4
...
-1073741824 1073741824

В этот момент a&b == 1073741824.Но сдвиг его влево на 1 - это то же самое, что умножение на 2, что даст 2147483648, что больше, чем INT_MAX.

Это неопределенное поведение.Система может сделать что угодно.Похоже, что в вашем случае, он сделал сдвиг бит, давая 0x80000000.В подписанном int это представляет INT_MIN.Поэтому в следующий раз в цикле вы пытаетесь сдвинуть влево отрицательное число, что снова является неопределенным поведением.Ваша система решила рассматривать это как исключение.

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