CODEWITHSUNDEEP
java
user3663882
user3663882

Reputation: 7357

Understanding unsigned right shift

The JLS 15.19 describes the formula for >>> operator.

The value of n >>> s is n right-shifted s bit positions with zero-extension, where:

If n is positive, then the result is the same as that of n >> s.

If n is negative and the type of the left-hand operand is int, then the result is equal to that of the expression (n >> s) + (2 << ~s).

If n is negative and the type of the left-hand operand is long, then the result is equal to that of the expression (n >> s) + (2L << ~s).

Why does n >>> s = (n >> s) + (2 << ~s), where ~s = 31 - s for int and ~s = 63 - s for long?

Upvotes: 3

Views: 655

Answers (2)

Paul Boddington
Paul Boddington

Reputation: 37645

If n is negative it means that the sign bit is set.

>>> s means shift s places to the right introducing zeros into the vacated slots.

>> s means shift s places to the right introducing copies of the sign bit into the vacated slots.

E.g.

10111110000011111000001111100000 >>> 3 == 00010111110000011111000001111100

10111110000011111000001111100000 >>  3 == 11110111110000011111000001111100

Obviously if n is not negative, n >> s and n >>> s are the same. If n is negative, the difference will consist of s ones at the left followed by all zeros.

In other words: 

(n >>> s) + X == n >> s        (*)

where X consists of s ones followed by 32 - s zeros.

Because there are 32 - s zeros in X, the right-most one in X occurs in the position of the one in 1 << (32 - s), which is equal to 2 << (31 - s), which is the same as 2 << ~s (because ~s == -1 - s and shift amounts work modulo 32 for ints).

Now what happens when you add 2 << ~s to X? You get zero! Let's demonstrate this in the case s == 7. Notice that the the carry disappears off the left.

  11111110000000000000000000000000
+ 00000010000000000000000000000000
  ________________________________
  00000000000000000000000000000000

It follows that -X == 2 << ~s. Therefore adding -X to both sides of (*) we get

n >>> s == (n >> s) + (2 << ~s)

For long it's exactly the same, except that shift amounts are done modulo 64, because longs have 64 bits.

Upvotes: 2

Vitruvie
Vitruvie

Reputation: 2327

Here is some additional context that will help you understand pbabcdefp's answer if you don't already know the basics he assumes:

To understand bitwise operators you must think about numbers as strings of binary digits, eg. 20 = 00010100 and -4 = 11111100 (For the sake of clarity and not having to write so many digits I will be writing all binary numbers as bytes; ints are the same but four times as long). If you are unfamiliar with binary and binary operations, you can read more here. Note how the first digit is special: It makes numbers negative, as if it had a place value (remember elementary math, the ones/tens/hundreds places?) of the most negative number possible, so Byte.MIN_VALUE = -128 = 1000000, and setting any other bit to 1 always increases the number. To easily read a negative number such as 11110011, know that -1 = 11111111, then read the 0s as if they were 1s in a positive number, then that number is how far away you are from -1. So 11110011 = -1 - 00001100 = -1 - 12 = -13.

Also understand that ~s is bitwise NOT: It takes all the digits and flips them, this is actually equivalent to ~s = -1 - s. Eg ~5 (00000101) is -6 (11111010). Observe how my suggested method for reading negative binary numbers is simply a trick to be able to read the bitwise NOT of the number rather than the number itself, which is easier for negative numbers close to zero because those numbers have fewer 0s than 1s.

Upvotes: 2

Related Questions