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)?

Solution 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 <<.

Solution 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

Solution 3

Because >> is defined as an arithmetic right shift, which preserves the sign. To get the effect you expect, use a logical right shift, the >>> operator.

Comments

[Vishy]

BTW, you can use >>> -1 and it will work for int and long types.

[user207421]

It doesn't really 'put 1', it just preserves the sign bit, whatever it is.

[user207421]

A simpler answer is both more correct and more help. The operator doesn't look to see whether the operand is negative or positive and then do two different things.

[user207421]

Please stick to the point and keep personalities out of it. Your explanation is twice as complex as necessary, and judging by your comment to @AlvinWong's answer you still don't understand why.

[user207421]

You could always try simplifying your answer, as suggested. I don't know why it's such a mystery. I've given you some wording: 'It just preserves the sign bit, whatever it is', and there are other correct answers to look at as well. Then you might even get some up-votes. The effect you describe occurs all right, but not in the way you described. You seem to be having trouble grasping this point.

[Stephen C]

@GrijeshChauhan - I agree with EJP. This answer is contradicting itself, and is very confusing.

[Grijesh Chauhan]

Ok what I was trying to say you written in one word preserves the sign that is good.

[user207421]

@GrijeshChauhan I meant for you to improve this answer. That was the reason for my original comment, and the whole conversation.

[Mmmh mmh]

What happens if you do 10101010 << 1? 11010100 or 01010100?

[Mmmh mmh]

I mean, is By the way, both arithmetic shift and logical shift have the same result, so there is only one left shift << really true?

[Robert Lewis]

Don't really like the term "sign extension", which to me is what happens when you copy a signed value into a larger word size. "Sign copying" or "sign preserving" seems more like it.

[Ajay]

Thank you for the detail description. You made my day.