How to reverse bits (big endian to little endian)?
Hi,
I have a problem with some bits. I have two bytes (surprise surprise) with 12 bits (they are padded with four zeros). The bytes SHOULD look like this (x and n represent bits):
| x n x n x n x n | x n x n 0 0 0 0 |
However, they are coming in as such:
| n x n x n x n x | 0 0 0 0 n x n x |
Obviously, this is backwards. I am trying to figure out how to basically reverse the bits so I can manipulate them correctly. I've tried looking at two's complement, bit shifting, bitwise operations, etc., and I don't know how to do this. I found an external library that apparently can do this, but at this point, I'm just dying to know how the algorithm works; I don't just want a reverse() method.
Can anyone offer any advice/tutorials/whatever?
Thanks
[803 byte] By [
Djaunla] at [2007-11-27 11:58:21]
Off-the-cuff, try this out (for integers, you'll have to modify for smaller types) ... may also have syntax errors:
public static int reverseBits(int in)
{
int out = 0;
for (int ii = 0 ; ii < 32 ; ii++)
{
int bit = (in & 1);
out = (out << 1) | bit;
in >> 1;
}
}
It works by shifting the rightmost bit off the input, and "appending" it to the output. Once you go through all 32 bits, you should have the number reversed.
Integer.reverse()
Long.reverse()
seem to be helpful.
There is no Byte.reverse() or Short.reverse(), but Integer.reverse()
can come to rescue, I suppose.
You can also convert big to little and vice versa using java.nio ByteBuffer's order method.
Well I have seen those methods, but I was really **** curious about the algorithm.
@kdgregory: thanks a lot for the code example. It did have a few errors (no return statement, "in >> 1" is not a statement), but I modified it a bit to accommodate for a byte input, and it seems to work fine. Here it is:
public static byte reverseBits(byte in) {
byte out = 0;
for (int ii = 0 ; ii < 8 ; ii++) {
byte bit = (byte)(in & 1);
out = (byte)((out << 1) | bit);
in = (byte)(in >> 1);
}
return out;
}
Figuring out how it works is another matter! I have the basic idea, but I am confused about a few things.
byte bit = (byte)(in & 1);
What is the purpose of ANDing the input byte with 1? Does that not give the exact same result? Is this to deal with the signed bit?
Actually, the rest kind of makes sense. I'll have to do one by hand just so I can be sure I understand it. That'll be a fun time sink.
Thanks for the replies.
Here is the Sun implementation of Integer.reverse().
Go figure!
public static int reverse(int i) {
// HD, Figure 7-1
i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
i = (i << 24) | ((i & 0xff00) << 8) |
((i >>> 8) & 0xff00) | (i >>> 24);
return i;
}
The preceeding implementation (and other very interesting low-level ones) can be found here:
http://aggregate.org/MAGIC/
Just thought i'd add my method:
public static int littleEndianToInt(byte abyte0[])
{
if(abyte0 == null)
throw new IllegalArgumentException("parameter cannot be null.");
if(abyte0.length != 4)
{
throw new IllegalArgumentException("parameter must be a 4-byte array.");
} else
{
int i = abyte0[3] << 24 & 0xff000000;
i |= abyte0[2] << 16 & 0xff0000;
i |= abyte0[1] << 8 & 0xff00;
i |= abyte0[0] & 0xff;
return i;
}
}
> byte bit = (byte)(in & 1);
>
> What is the purpose of ANDing the input byte with 1?
> Does that not give the exact same result? Is this to
> deal with the signed bit?
It extracts the low-order bit from the byte. Here's how the whole algorithm works, for a 4-bit value:
inoutbit
101101
10111
10110
11101
01101n/a
Incidentally, I'd recommend going with Integer.reverse() if you're using 1.5, along with appropriate masking ... I didn't know that it was available.
> Just thought i'd add my method:
>
> public static int littleEndianToInt(byte
> abyte0[])
>{
>if(abyte0 == null)
> throw new IllegalArgumentException("parameter
> cannot be null.");
>if(abyte0.length != 4)
> {
> throw new
> IllegalArgumentException("parameter must be a 4-byte
> array.");
> } else
> {
> int i = abyte0[3] << 24 & 0xff000000;
> i |= abyte0[2] << 16 & 0xff0000;
> i |= abyte0[1] << 8 & 0xff00;
> i |= abyte0[0] & 0xff;
> return i;
>}
This reverses the bytes, not the bits.
For understanding Kdgregory's solution is the best.
For efficiency and use, Sun's reverse();
Understanding Sun's magic, which I did after the initial surprise,
can also sharpen your bit manipulation techniques.
