8

Why if 

int x = -1 // binary: 11111111111111111111111111111111
x = x >>> 31;

we have 00000000000000000000000000000001

but if 

int x = -1
x = x >>> 32;

we have 11111111111111111111111111111111 (again -1)

but not 00000000000000000000000000000000 ?

Rohit Jain
  • 209,639
  • 45
  • 409
  • 525
ses
  • 13,174
  • 31
  • 123
  • 226

3 Answers3

13

From Section 15.19 of JLS:

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 (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.

Emphasis mine. So:

x >>> n

is equivalent to: 

x >>> n & 0x1f  // or x >>> n % 32

So, x >>> 32 is equivalent to x >>> 32 & 0x1f <==> x >>> 0 == x.

So the Rule of Thumb is, whenever you shift a number by a multiple of 32(int is 32 bits), you get back the same value.

Rohit Jain
  • 209,639
  • 45
  • 409
  • 525
  • IMHO, this is a REALLY bad choice! Mathematically, the two are absolutely NOT equivalent. Now, if this was a **rotate** operation, rather than a shift, ok. But this? Who came up with that? – Markus A. Feb 11 '13 at 17:43
  • How I should shift >>> to have a 0 as a result? – ses Feb 11 '13 at 17:43
  • 4
    This is specified by [JLS 15.19](http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19). But the reasoning is probably that people expect shifts to be blazing fast operations, and this is the only implementation that can be branch-free on almost every processor. – Louis Wasserman Feb 11 '13 at 17:44
  • 1
    @MarkusA... Since `int` in Java is `32` bits, you can only shift by a maximum of `31` right. So, this doesn't mean that we can avoid shifting by `32`. So, what would you expect to happen when an int is shifted by 32 or more? The result will be always 0, if you go mathematically? That is why this way of shifting came up. – Rohit Jain Feb 11 '13 at 17:44
  • @MarkusA. No. You need to check if the right operand is more than 31 and then return a flat zero with no further consideration. – Marko Topolnik Feb 11 '13 at 17:50
  • @RohitJain Of course you can shift more than 31. All it means is move every bit right 32 times and drop all the bits that fall off at the end. You can keep doing that forever. And yes, if the operand is more than 31, this should always return 0, and NOT something else... – Markus A. Feb 11 '13 at 18:25
  • Imagine if 10 divided by 15 was 2, because as 15 is bigger than 10, you instead simply divide by 15%10. This is just plain ridiculous... – Markus A. Feb 11 '13 at 18:27
  • @MarkusA.. And now you are mixing up `>>>` with `division`, that is not simply right. `>>>` has some other rules, that are specific to it. See the JLS section I linked. – Rohit Jain Feb 11 '13 at 18:29
  • @RohitJain I know they are different. I'm not mixing anything up. It's just an equally ridiculous example. All I'm saying is that I find their decision problematic. `>>> n` should be equivalent to `/ 2^n` (for positive numbers). And the following equality should hold: `>>> a >>> b == >>> (a+b)`. I don't think any processor implements it this way either. So, they spend extra clock cycles to mess up a result. Unfortunately I don't have a link to a truly authoritative source right now, but at least Wikipedia doesn't mention anything about modulo 32: http://en.wikipedia.org/wiki/Arithmetic_shift – Markus A. Feb 11 '13 at 18:35
  • @MarkusA.. Well, I'm not the right person to comment on that. Now you are targetting the original Java creators. I'm far away from them, and I can't say why this is designed like this. Only they can tell. – Rohit Jain Feb 11 '13 at 18:37
  • @RohitJain Since some processors don't have a distinction between >>> and >>, they probably use some lookup-table for the and masks they need to simulate >>> on such platforms. I'm sure they had some reason. This is just really painful to see. Now, I need to go through all my code and check that, if I ever calculate the shift operand anywhere, I place an if-statement to catch this error. WOW... Just noticed! Things work differently again, if the operand is negative!!! -1 >>> -3 == 7!!!! WTF??? And that's not even covered in the JLS! – Markus A. Feb 11 '13 at 18:48
  • @MarkusA.. Yeah sure that is listed in JLS. `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 (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive. ` – Rohit Jain Feb 11 '13 at 19:05
  • @MarkusA.. So, `-1 >>> -3` is equivalent to : `-1 >>> 29`, since `-3 & 0x1f = 29`. So, `-1 >>> 29 = 7`. – Rohit Jain Feb 11 '13 at 19:06
  • @MarkusA.. I've just quoted that thing in a simple language using `%` in my answer. masking by `0x1f` is same as `modulus by 32`. – Rohit Jain Feb 11 '13 at 19:07
2

When applying the bit-shift operation only the lowest 5 bits of the right-hand operand are considered. Since 32 === 0 // mod 32, the result is no shifting.

Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
0

Spent an entire day breaking my head over why a long l = i << 32 behaved strangely, then wrote some basic tests, had the WTF moment, and then chnged to long l = (long) i << 32 for it to work.

My only add to Rohit's answer is the reason why this is so. From IA-32 Intel Architecture Software Developer’s Manual 3:

The 8086 does not mask the shift count. However, all other IA-32 processors (starting with the Intel 286 processor) do mask the shift count to 5 bits, resulting in a maximum count of 31. This masking is done in all operating modes (including the virtual-8086 mode) to reduce the maximum execution time of the instructions

sr33
  • 83
  • 4