Why does a left shift create a negative value?

Hi!

Just learning left shift. I’m confused by why the value becomes a negative value. Could you help?

class MultByTwo {
 public static void main(String args []) {
  int i;
  int num = 0xFFFFFFE;

  for (i=0;i<4;i++) {
   num = num << 1;
   System.out.println(num);
  }
 }
}

This outputs

536870908
1073741816
2147483632
-32

Why does it produce -32 at the end?

Thanks,

Christian

It’s because you’ve encountered an integer overflow.

In Java, an int type can hold any value between -2147483648 and 2147483647. (int is a 32-bit signed type, so these values are -(2^31) and (2^31)-1 respectively. The left-most bit is used to denote whether the value is positive or negative.)

In your code, at the point where i = 2, your value of num is 2147483632 - 15 lower than the max value int can hold.

This may be clearer if we review the binary:

i=0  536870908   =  11111111111111111111111111100     (29 bits to store number)
i=1  1073741816  =  111111111111111111111111111000    (30 bits to store number)
i=2  2147483632  =  1111111111111111111111111110000   (31 bits to store number)
i=3  -32         =  11111111111111111111111111100000  (32 bits to store number!)

As soon as the left-most 1 hits the 32nd bit, it becomes the bit which denotes sign and makes your number negative.

You can change your code to this:

class MultByTwo {
 public static void main(String args []) {
  int i;
  long num = 0xFFFFFFE;

  for (i=0;i<4;i++) {
   num = num << 1;
   System.out.println(num);
  }
 }
}

which won’t have the same problem, because long uses 8 bytes (64-bit) to store the number instead of the 4 bytes (32-bits) which int uses. Instead, you’ll get this:

536870908
1073741816
2147483632
4294967264

:slight_smile:

Edit: Here’s some more info on integer overflow.

1 Like

Thank you!

Why does it become -32 in particular? And why does it become negative? All the other values have a 1 as their left most bit.

Thanks,

Christian

1 Like

I’m going to answer these in reverse, as it’ll make more sense that way.

  1. All the other values have a 1 as their left most bit.

Not exactly. This is true if we simply write out the values, but it is false if we look at each number in the context of it being a 4-byte (32-bit) value. For example:

i=1  1073741816  =  111111111111111111111111111000    (30 bits to store number)

If we view the entirety of the 32-bit space this number can occupy, we see this:

image

Here we can see the entirety of the 32-bit space, with the binary representation of your number in the bits highlighted in green. There are two leading zeroes at the start of the number, in yellow. The left-most bit is a zero, hence the number is positive.

  1. Why does it become negative?

In Java, the int type is signed. Everything to a computer comes down to bits - 1 or 0. There is no concept of a negative sign -, so if the computer needs to be aware of negative values we need some way of telling it about them.

Java is seeing -32 as the following.
image

As the most significant (left most) bit is a 1, the number is a negative. This is by convention; the computer does everything in 1s and 0s - there’s no concept of encoding a negative sign, so a bit is reserved to indicate this instead.

  1. Why does it become -32 in particular?

Java uses a method of representing negative numbers which is called “Two’s complement”. I’ll link to a fuller description of that at the end, but for now I’ll just cover the basics.

Let's change 32 to -32 by converting to Twos complement representation

00000000000000000000000000100000    # 32 in binary
11111111111111111111111111011111    # invert (flip) each bit. 
11111111111111111111111111100000    # add one.

The value represented by 11111111111111111111111111100000 is essentially the same as taking -(2^31) - the left-most bit - and then adding the positive value of each subsequent 1, like so:

-2147483648 
+ 1073741824 + 536870912 + 268435456 + 134217728 + 67108864 + 33554432 + 16777216 
+ 8388608 + 4194304 + 2097152 + 1048576 + 524288 + 262144 + 131072 + 65536 + 32768 
+ 16384 + 8192 + 4096 + 2048 + 1024 + 512 + 256 + 128 + 64 + 32
= -32

You end up with -32.

Hope that clears it up a bit.

Also, here’s the link for more info on Two’s complement representation.

:slight_smile:

1 Like