Java: Right Shift on Negative Number

Java: right shift on negative number

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

why the result of a negative number in shift operator is different from the normal division?

The shift operator drops any mathematical fraction by taking the floor, not the truncation. The JLS, Section 15.19, states:

The value of n >> s is n right-shifted s bit positions with sign-extension. The resulting value is floor(n / 2s). For non-negative values of n, this is equivalent to truncating integer division, as computed by the integer division operator /, by two to the power s.

The floor of -3.75 is -4 whereas truncation would have yielded -3.

When the value is right-shifted, bits are lost as they are shifted "off the end" of the value. This is what is responsible for the floor operation.

-15: 11110001
 -4: 11111100 // The rightmost 1 bit above is lost, resulting in what looks like the floor function.

Shifted by negative number in java

From the JLS, section 15.19 (Shift Operators):

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.

Now -63 & 0x1f == 1, So this is actually a shift by 1 to the right, hence the answer of 4.

unsigned right shift by negative number in Java

It seems counter-intuitive, but when shifting an int, only the last 5 bits of the shift amount are used, according to the JLS, Section 15.19.

If the promoted type of the left-hand operand is int, then 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.

This means that -3 only has the last 5 bits used, or 29. Here's -3 in bits to show what's going on:

11111111 11111111 11111111 11111101

The last 5 bits are 11101, or 29 in decimal.

The right-shift distance is 29, which means that the first 3 bits are kept and shifted all the way to the right. Taking -37:

11111111 11111111 11111111 11011010

After the unsigned shift of 29 places, 7 is left:

00000000 00000000 00000000 00000111

As you can see, a negative shift amount is confusing at best. Try to avoid it and always attempt to use an actual number between 0 and 31 for the shift amount for shifting ints.

Shifting by Negative Numbers

<< (and other shift operators) only takes 5 least significant bits of its right operand for int, and 6 for long, because it makes no sense to shift int by more than 31.

In your case it's 0b10110 = 22.

Therefore 1 << (-10) is equivalent to 1 << 22.

Bit wise shift operator with shift by negative number

But if b is neagtive, shouldn't it be an error at runtime?

Not according to the Java Language Specification, section 15.19:

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.

So a shift of -32 actually ends up as a shift of 0, and a shift of -49 actually ends up as a shift of 15 - hence the results you saw.

Is right shifting undefined behavior for negative number in cpp and in java?

Yes. It is implementation-defined.

According to C++03 5.8/3 which defines right-shifting:

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has
an unsigned type or if E1 has a signed type and a nonnegative value,
the value of the result is the integral part of the quotient of E1
divided by the quantity 2 raised to the power E2. If E1 has a signed
type and a negative value, the resulting value is
implementation-defined.

For more information, see this link.

Why does right shift on positive number sometimes result in a negative number?

Use the zero-fill right shift operator (>>>) to always get a positive result:

const now = 1562143596806 // UNIX timestamp in millisecondsconsole.log(now >>> 8)

Signed and unsigned right shift seem to have the same behaviour

This is normal behavior. Any integer with a negative value has a binary representation starting with infinite 1s.

So if you start out with say: -3 the binary representation looks like this:

...11 1101

So if we right shift this by 2 we get

...11 1111

Now for the unsgined/signed right shift. This relies on the fact that we don't have infinite digits in our integer. So say we have an 8bit integer assigned as -3 it looks like this:

1111 1101

If we do a signed shift, it will look at the MSB (most significant bit, the most left one) and preserve the value of that when shifting. So a signed shift right by 3 looks like this:

1111 1111

On the contrary, a unsigned right shift will not check the MSB and just shift right and fill with zeroes resulting in this:

0011 1111

This is exactly what you're seeing but the output truncates the preceding zeroes away.

---

If you don't know why negative integers are stored that way, check this answer.

---

As for why (b & 0xff) >>> 5 behaves differently

Integers in java are 32bit, that means the binary representation will have 32 digits. Your -59 will look like the following binary representation:

1111 1111 1111 1111 1111 1111 1100 0101 == -59
0000 0111 1111 1111 1111 1111 1111 1110 == -59 >>> 5

If you now and this together with 0xff you get the following:

1111 1111 1111 1111 1111 1111 1100 0101 == -59
0000 0000 0000 0000 0000 0000 1111 1111 == 0xff
0000 0000 0000 0000 0000 0000 1100 0101 == -59 & 0xff
0000 0000 0000 0000 0000 0000 0000 0110 == (-59 & 0xff) >>> 5

---

Related Topics