java bit manipulation

Question

byte x = -1;
for(int i = 0; i < 8; i++)
{
    x = (byte) (x >>> 1);
    System.out.println("X: " + x);
}

As I understand it, java stores data in two's-complement, meaning -1 = 11111111 (according to wikipedia).

Also, from the java docs: "The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand. The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension. "

Which means that >>> would shift a 0 to the left most bit every time. So I expect this code to be

iteration: bit representation of x

0: 11111111

1: 01111111

2: 00111111

3: 00011111

...so on

However, my output is always X: -1, meaning (I guess) that >>> is putting the sign bit in the left most position. So I then try >>, and same result.

What's going on? I would expect my output to be: X: -1, x: 127, x: 63, etc.

Please help.

jbu

Answer 1

I'm not sure about this. But, my guess is that

x >>> 1

gets promoted to a int from byte, because the literal "1" is an int. Then what you are observing makes sense.

Answer 2

Whoever thought that bytes should be signed when Java was invented should be taken out and beaten with a wet stick of celery until they cry :-)

You can do what you want by casting up to an int and ensuring you never shift a 1 into the top bit, something like this:

byte x = -1;
int x2 = ((int)x) & 0xff;
for(int i = 0; i < 8; i++)
{
    x2 = (x2 >>> 1);
    System.out.println("X: " + x2);
}

Your particular problem is because >>> is casting up to an int to do the shift, then you're casting it back to a byte, as shown here:

byte x = -1;
int x2 = ((int)x) & 0xff;
int x3;
int x4 = x2;
for(int i = 0; i < 8; i++)
{
    x2 = (x2 >>> 1);
    System.out.println("X2: " + x2);
    x3 = (x >>> 1);
    x = (byte)x3;
    x4 = (x4 >>> 1);
    System.out.println("X: " + x3 + " " + x + " " + x4);
}

Which outputs:

X2: 127
X: 2147483647 -1 127
X2: 63
X: 2147483647 -1 63
X2: 31
X: 2147483647 -1 31
X2: 15
X: 2147483647 -1 15
X2: 7
X: 2147483647 -1 7
X2: 3
X: 2147483647 -1 3
X2: 1
X: 2147483647 -1 1
X2: 0
X: 2147483647 -1 0

You can clearly see that x and x3 don't work (even though x3 shifts correctly, casting it back to byte in x sets it to -1 again). x4 works perfectly.

Answer 3

I don't know why it doesn't work, but an easy way to clear the top bit is to & with (binary) 0111111:

x = (byte) (x >>> 1) & 0x7F;

Answer 4

Remember that:

• operands of bitwise operations are always promoted to at least an int!
• casts always involve sign extension.

So when you do (x >>> n), even though you defined x as a byte, for the purposes of the shift, it will be first converted to an int. If the byte being converted is negative, then all of the "extra bits" (so, the leftmost 24 bits of the resulting int) added to make it up to an int will be set to 1. Or put another way, if the original byte was -1, the thing you're actually shifting is -1 as an int, i.e. 32-bit number with all 32 bits set to 1. Shifting this right by 1-8 places will still result in the bottom 8 bits all set to 1, hence when you cast back to a byte, you end up with a byte with all 8 bits set to 1, or in other words, a byte value of -1.

Answer 5

The problem is, as told before (long time ago), that x get upcasted to int (sign-extended) before doing the shift.
Doing a "bit-to-bit" conversion should help:

byte x = -1;
for(int i = 0; i < 8; i++)
{
    x = (byte) ((x & 0xFF) >>> 1);
    System.out.println("X: " + x);
}