java Bit operations >>> shift

Question

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 ?

Verboten

Because shifts in Java are always modulo the length of the shifted value. – Fracas

That's REALLY good to know, considering it's just plain WRONG from a math point of view! – Setsukosett

Answer 1

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.

Gid

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? – Setsukosett

How I should shift >>> to have a 0 as a result? – Verboten

This is specified by 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. – Antre

@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. – Gid

@MarkusA. No. You need to check if the right operand is more than 31 and then return a flat zero with no further consideration. – Ivoryivorywhite

@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... – Setsukosett

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... – Setsukosett

@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. – Gid

@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: en.wikipedia.org/wiki/Arithmetic_shift – Setsukosett

@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. – Gid

@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! – Setsukosett

@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. – Gid

@MarkusA.. So, -1 >>> -3 is equivalent to : -1 >>> 29, since -3 & 0x1f = 29. So, -1 >>> 29 = 7. – Gid

@MarkusA.. I've just quoted that thing in a simple language using % in my answer. masking by 0x1f is same as modulus by 32. – Gid

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

Ivoryivorywhite

Answer 3

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

Juxtapose