С++ переполнение сдвига влево для отрицательных чисел
Как показано ниже, в коде есть ошибка. Когда ввод 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,
For unsigned a and for signed a with nonnegative values, the value of a >> b is the integer part of a/2b . For negative a, the value of a >> b is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative).
In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.
обратите внимание, что XOR не создает больше битов, чем операндов, поэтому он никогда не может переполниться (за исключением, вероятно, систем с представлением ловушек) Может ли XOR двух целых чисел выйти за пределы?. INT_MIT находится в пределах диапазона int, поэтому это не переполнение.
Первый a & b - это 1, как вы говорите, но вы находитесь в цикле while, который обновляет значения a и b, ошибка возникает на более поздней итерации.
для перестановки битов в C используется беззнаковые типы.
Ответы 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. Таким образом, в следующий раз в цикле вы пытаетесь сдвинуть влево отрицательное число, что опять-таки является неопределенным поведением. Ваша система решила рассматривать это как исключение.
В общем, если вы выполняете битовые манипуляции, вам лучше всего использовать беззнаковые типы.
Большое спасибо! В этом случае, когда a = -1 и b = 1, как мы будем обрабатывать сдвиг влево? По сути, функция getSum() вычисляет a + b с помощью битовых манипуляций.
приведение к неподписанному.
Спасибо, а не могли бы вы объяснить немного подробнее?
Мы знаем, что существует более одного способа представления отрицательного числа в двоичном виде, а не только 0xFFFFFFFF en.wikipedia.org/wiki/Signed_number_representations.