Thursday, February 19, 2009

Bit manipulation in Java

I have always had a hard time remembering rules of bit manipulation in Java.

So, when someone asked this question on Stackoverflow.com, I knew he had to do masking, but I forgot why.

I decided to look up bit wise operations on Wikipedia to refresh my memory. However, this time I am also blogging the answer so I don't forget (yet another use of blogging :-) ).

There are two types of bit shift operations: arithmetic shift, and logical shift. An arithmetic right shift preserves the sign bit, while logical shifts always insert a zero.

Representing -1 as a signed byte we get: 11111111

-1 >> 1 gives us: 11111111
-1 >>> 1 gives us: 01111111


so by this logic (-1 >>> 8) should give us 00000000 which is 0

Well not so:

byte b = -1;
System.out.println("-1 >>> 8 = " + (b >>> 8));

The output I get is:

-1 >> 8 = 16777215

Hmmm. what just happened? Java converted the signed byte into a signed int, and then did an arithmetic right shift of 8 bits.

So Java converted -1 to a signed 32 bit integer:
1111111111111111111111111111111

Then did a logical right shift of 8 bits getting
00000000111111111111111111111111

which is: 16777215 in base 10

ok, let's try casting the output back into a byte

byte b = -1;
System.out.println("-1 >>> 8 = " + (byte)(b >>> 8));

The output is:

-1 >> 8 = -1

That did not help because the lower 8 bits of the answer are still all 1's, so casting to a byte gives us -1.

ok, so how do I get the 0 I was after? We can get it by bit masking the byte.

byte x = -1;
System.out.println("-1 >>> 8 = " + ((x&0xFF) >>> 8));


Running the above code gives us an output of:

-1 >>> 8 = 0

So what just happened? b is still converted into a signed 32 bit integer, giving us:
1111111111111111111111111111111


but then we mask it with 0xFF, which gives us
0000000000000000000000011111111


Now when we do a logical right shift of 8 bits, we get
0000000000000000000000000000000


I hope this post helps me remember bit wise operations in Java, and I hope it helps you too. If you have a problem remembering things like I do, you may want to create a little example code and blog about it yourself.

1 comment:

Stacie Huudson said...

Build yourself a class that knows how to peruse and compose bits to a stream instead of the usual Java input and output streams that thoroughly understand perusing and composing bytes.You'll see it accommodating to discrete out the operations of "give me the next N bits" and "advance the cursor by M bits."For instance,this would permit you to peruse enough data to cover the longest possible Huffman code.When you discover the true length of the Huffman code you simply read,then you advance the cursor by just that numerous bits.A class like that additionally gives you a chance to attempt to compartmentalize the uglier aspects of bit manipulation into a fairly small chunk of code.

,,,,,,,,,,,,,,,,,,,,,,,,,
hidden object game