Shift operator in Java bizarre program output

Question

I came across the following program and it behaving in unexpected manner.

public class ShiftProgram
{
      public static void main(String[] args)
      {
             int i = 0;
             while(-1 << i != 0)
                   i++;
             System.out.println(i);
      }
}

If we think about this program output, when it reaches 32 while loop condition should return false and terminate and it should print 32.

If you ran this program, it does not print anything but goes into an infinite loop. Any idea whats going on? Thank you in advance.

Answer 1

Have you tried printing out (-1 << i) in the loop to see what's going wrong? If you do, you'll see that it goes:

-1 << 0 = -1
-1 << 1 = -2
-1 << 2 = -4
-1 << 3 = -8
-1 << 4 = -16
-1 << 5 = -32
-1 << 6 = -64
-1 << 7 = -128
-1 << 8 = -256
-1 << 9 = -512
-1 << 10 = -1024
-1 << 11 = -2048
-1 << 12 = -4096
-1 << 13 = -8192
-1 << 14 = -16384
-1 << 15 = -32768
-1 << 16 = -65536
-1 << 17 = -131072
-1 << 18 = -262144
-1 << 19 = -524288
-1 << 20 = -1048576
-1 << 21 = -2097152
-1 << 22 = -4194304
-1 << 23 = -8388608
-1 << 24 = -16777216
-1 << 25 = -33554432
-1 << 26 = -67108864
-1 << 27 = -134217728
-1 << 28 = -268435456
-1 << 29 = -536870912
-1 << 30 = -1073741824
-1 << 31 = -2147483648
-1 << 32 = -1
-1 << 33 = -2
-1 << 34 = -4
-1 << 35 = -8
-1 << 36 = -16
[.. etc ..]

According to the language specification:

The value of n<<s is n left-shifted s bit positions; this is equivalent (even if overflow occurs) to multiplication by two to the power s.

... so the result will always remain negative.

That document also tells you that:

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f. The shift distance actually used is therefore always in the range 0 to 31, inclusive.

So if you use a shift of 32, that's interpreted as a shift of 32 & 0x1f, which is 0. -1 shifted by 0 is still just -1, not 0.

Answer 2

The shift count is interpreted modulo the number of bits in an int (32), and so i << 32 is just i << 0 which is i. Thus, you will never get 0 as the result. My source for that is http://www.janeg.ca/scjp/oper/shift.html. If you do something like int n = -1; while (n != 0) {i++; n <<= 1;}, it will eventually reach 0 like you want.