Java: right shift on negative number

Question

I am very confused on right shift operation on negative number, here is the code.

int n = -15; System.out.println(Integer.toBinaryString(n)); int mask = n >> 31; System.out.println(Integer.toBinaryString(mask)); 

And the result is:

11111111111111111111111111110001 11111111111111111111111111111111 

Why right shifting a negative number by 31 not 1 (the sign bit)?

Answer 1

Because in Java there are no unsigned datatypes, there are two types of right shifts: arithmetic shift >> and logical shift >>>. http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

Arithmetic shift >> will keep the sign bit.

Unsigned shift >>> will not keep the sign bit (thus filling 0s).

(images from Wikipedia)

---

By the way, both arithmetic left shift and logical left shift have the same result, so there is only one left shift <<.

Answer 2

Operator >> called Signed right shift, shift all the bits to right a specified number of times. Important is >> fills leftmost sign bit (Most Significant Bit MSB) to leftmost bit the after shift. This is called sign extension and serves to preserve the sign of negative numbers when you shift them right.

Below is my diagrammatic representation with an example to show how this works (for one byte):

Example:

i = -5 >> 3;  shift bits right three time  

Five in two's complement form is 1111 1011

Memory Representation:

 MSB +----+----+----+---+---+---+---+---+ |  1 |  1 | 1  | 1 | 1 | 0 | 1 | 1 |    +----+----+----+---+---+---+---+---+    7    6   5    4   3   2   1   0     ^  This seventh, the left most bit is SIGN bit   

And below is, how >> works? When you do -5 >> 3

                        this 3 bits are shifted                           out and loss  MSB                   (___________)       +----+----+----+---+---+---+---+---+ |  1 |  1 | 1  | 1 | 1 | 0 | 1 | 1 |    +----+----+----+---+---+---+---+---+   | \                 \     |  ------------|     ----------|   |              |               |   ▼              ▼               ▼ +----+----+----+---+---+---+---+---+ |  1 |  1 | 1  | 1 | 1 | 1 | 1 | 1 | +----+----+----+---+---+---+---+---+ (______________)  The sign is          propagated 

Notice: the left most three bits are one because on each shift sign bit is preserved and each bit is right too. I have written The sign is propagated because all this three bits are because of sign(but not data).

Also because of three right shift right most three bits are losses out.

The bits between right two arrows are exposed from previous bits in -5.

I think it would be good if I write an example for a positive number too. Next example is 5 >> 3 and five is one byte is 0000 0101

                        this 3 bits are shifted                           out and loss  MSB                   (___________)       +----+----+----+---+---+---+---+---+ |  0 |  0 | 0  | 0 | 0 | 1 | 0 | 1 |    +----+----+----+---+---+---+---+---+   | \                 \     |  ------------|     ----------|   |              |               |   ▼              ▼               ▼ +----+----+----+---+---+---+---+---+ |  0 |  0 | 0  | 0 | 0 | 0 | 0 | 0 | +----+----+----+---+---+---+---+---+ (______________)  The sign is          propagated 

See again I writes The sign is propagated, So leftmost three zeros are due to sign bit.

So this is what operator >> Signed right shift do, preserves the sign of left operand.

[your answer]
In your code, you shifts -15 to right for 31 times using >> operator so your right most 31 bits are loosed and results is all bits 1 that is actually -1 in magnitude.

Do you notice that In this way -1 >> n is equivalent to not a statement.
_{I believe if one do i = -1 >> n it should be optimized to i = -1 by Java compilers, but that is different matter}

Next, It would be interesting to know in Java one more right shift operator is available >>> called Unsigned Right Shift. And it works logically and fills zero from left for each shift operation. So at each right shift you always get a Zero bit on left most position if you use unsigned right shift >>> operator for both Negative and Positive numbers.

Example:

i = -5 >>> 3;  Unsigned shift bits right three time  

And below is my diagram that demonstrates how expression -5 >>> 3 works?

                        this 3 bits are shifted                           out and loss  MSB                   (___________)       +----+----+----+---+---+---+---+---+ |  1 |  1 | 1  | 1 | 1 | 0 | 1 | 1 |    +----+----+----+---+---+---+---+---+   | \                 \     |  ------------|     ----------|   |              |               |   ▼              ▼               ▼ +----+----+----+---+---+---+---+---+ |  0 |  0 | 0  | 1 | 1 | 1 | 1 | 1 | +----+----+----+---+---+---+---+---+ (______________)   These zeros   are inserted   

And you can notice: this time I am not writing that sign bits propagated but actually >>> operator insert zeros. Hence >>> doesn't preserves sign instead do logical right shift.

In my knowledge unsigned right shift is useful in VDU (Graphics programming),Although I haven't used it but read it some where in past.

I would suggest you read this: Difference between >>> and >> : >> is arithmetic shift right, >>> is logical shift right.

Edit:

Some interesting about Unsigned Right Shift Operator >>> operator.

• The unsigned right shift operator >>> produces a pure value that is its left operand right-shifted with zero 0 extension by the number of bits specified by its right operand.

• Like >> and <<, operator >>> also operator never throws an exception.

• The type of each operand of the unsigned right shift operator must be an integer data type, or a compile-time error occurs.

• The >>> operator may perform type conversions on its operands; unlike arithmetic binary operators, each operand is converted independently. If the type of an operand is byte, short, or char, that operand is converted to an int before the value of the operator is computed.

• The type of the value produced by the unsigned right shift operator is the type of its left operand. LEFT_OPERAND >>> RHIGT_OPERAND

• If the converted type of the left operand is int, only the five least significant bits of the value of the right operand are used as the shift distance. (that is 2⁵ = 32 bits = number of bit in int)
  So, the shift distance is in the range 0 through 31.

  Here, the value produced by r >>> s is the same as:

  s==0 ? r : (r >> s) & ~(-1<<(32-s)) 

• If the type of the left operand is long, then only the six least significant bits of the value of the right operand are used as the shift distance.(that is 2⁵ = 64 bits = number of bit in long)

  Here, the value produced by r >>> s is the same as the following:

  s==0 ? r : (r >> s) & ~(-1<<(64-s)) 

A Interesting Reference: [Chapter 4] 4.7 Shift Operators