Как работает сдвиг влево на 31 (1 << 31) для получения максимального значения int? Вот мои мысли и некоторые объяснения, которые я нашел в Интернете

Question

Я довольно новичок в битовых манипуляциях и пытаюсь понять, как (1 << 31) - 1 работает.

Сначала я знаю, что 1 << 31 является

1000000000000000000000000000

и я знаю, что это на самом деле дополнение минимального значения int, но когда я попытался выяснить (1 << 31) - 1, я нашел объяснение, что это просто

10000000000000000000000000000000 - 1 = 01111111111111111111111111111111

Я был почти искушен верить этому, так как это действительно просто. Но так ли это на самом деле? Если это не так, почему это так?

Моя первоначальная мысль заключалась в том, что реальный процесс должен быть следующим: дополнение двух к

11111111111111111111111111111111

затем (1 << 31) - 1 =

(1)01111111111111111111111111111111

крайний левый 1 оставлен, тогда мы имеем максимальное значение int.

Я действительно не понимаю, какой из них прав.

Answer 1

Это оба! 1 << 31 это:

1000 0000 0000 0000 0000 0000 0000 0000

Вычитание 1 дает:

0111 1111 1111 1111 1111 1111 1111 1111

Одна из приятных особенностей компоновки чисел со знаком - это то, что сложение и вычитание - это те же операции, что и для чисел без знака. Таким образом, 10000... 000 представляет отрицательное число в дополнении к двум, наибольшее отрицательное число, которое в данном случае составляет -2 147 483 648, и вычитание 1 из него вызывает переход к наибольшему положительному числу - 2 147 483 647, но два числа дополнения расположены так что мы можем притвориться, что это число без знака, так что вычитание несложно. Вычитая 1 из 10000... 000 просто сбрасывает ведущую 1 на 0 и занимает кучу 1 с, так же как в десятичной системе вы получаете кучу 9 с: 10000 - 1 = 9999.

Это также верно, что математически, (a - b) такой же как (a + (-b))так что мы можем сделать (1 << 31) + (-1) вместо:

  1000 0000 0000 0000 0000 0000 0000 0000    (1 << 31)
  1111 1111 1111 1111 1111 1111 1111 1111    (-1)
-----------------------------------------
1 0111 1111 1111 1111 1111 1111 1111 1111    +

  0111 1111 1111 1111 1111 1111 1111 1111    (truncate)

1 выполняется из верхнего уровня и теряется, когда результат усекается обратно в 32-разрядное целое число.

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

Существуют и другие способы генерирования этого шаблона, например, ~(1 << 31), а также (-1 >>> 1) (где >>> означает логический сдвиг вправо), который не зависит от ширины целого числа.