How does 1 left shift by 31 (1 << 31) work to get maximum int value? Here are my thoughts and some explanations I found online

HM9527 picture HM9527 · Aug 29, 2016 · Viewed 10k times · Source

I'm fairly new to bit manipulation and I'm trying to figure out how (1 << 31) - 1 works.

First I know that 1 << 31 is

1000000000000000000000000000

and I know it's actually complement of minimum int value, but when I tried to figure out (1 << 31) - 1, I found an explanation states that, it's just

10000000000000000000000000000000 - 1 = 01111111111111111111111111111111

I was almost tempted to believe it since it's really straightforward. But is this what really happening? If it's not, why it happens to be right?

My original thought was that, the real process should be: the two's complement of -1 is

11111111111111111111111111111111

then (1 << 31) - 1 =

(1)01111111111111111111111111111111

the leftmost 1 is abandoned, then we have maximum value of int.

I'm really confused about which one is right.

Answer

Boann picture Boann · Aug 29, 2016

It's both! 1 << 31 is:

1000 0000 0000 0000 0000 0000 0000 0000

Subtracting 1 gives:

0111 1111 1111 1111 1111 1111 1111 1111

One of the nice features about the two's complement layout of signed numbers is that addition and subtraction are exactly the same operations as they are for unsigned numbers. So 10000...000 represents a negative number in two's complement, the largest negative number, which is -2,147,483,648 in this case, and subtracting 1 from it causes wrap-around to the largest positive number, 2,147,483,647, but two's complement numbers are arranged so that we can pretend it's an unsigned number instead, so the subtraction is uncomplicated. Subtracting 1 from 10000...000 simply drops the leading 1 to a 0, and borrows a bunch of 1s, same as in decimal you get a bunch of 9s: 10000 - 1 = 9999.

It's also true that mathematically, (a - b) is the same as (a + (-b)), so we can do (1 << 31) + (-1) instead:

  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)

A 1 is carried out of the high end, and lost once the result is truncated back into a 32-bit integer.

Either way, that pattern, with a single 0 at the high end, then filled by 1s, is the representation of the maximum positive value for a two's complement integer of any width.

There are other ways to generate that pattern if you prefer, such as ~(1 << 31), and (-1 >>> 1) (where >>> means logical shift right) which is agnostic of the width of the integer.