9 Replies Latest reply on Jul 27, 2007 8:56 PM by baftos

# 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
• ###### 1. Re: How to reverse bits (big endian to little endian)?
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.
• ###### 2. Re: How to reverse bits (big endian to little endian)?
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.
• ###### 3. Re: How to reverse bits (big endian to little endian)?
You can also convert big to little and vice versa using java.nio ByteBuffer's order method.
• ###### 4. Re: How to reverse bits (big endian to little endian)?
Well I have seen those methods, but I was really damn 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.
• ###### 5. Re: How to reverse bits (big endian to little endian)?
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;
}``````
• ###### 6. Re: How to reverse bits (big endian to little endian)?
The preceeding implementation (and other very interesting low-level ones) can be found here:
http://aggregate.org/MAGIC/
• ###### 7. Re: How to reverse bits (big endian to little endian)?
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;
}
}``````
• ###### 8. Re: How to reverse bits (big endian to little endian)?
``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:
``````in      out     bit
1011    0       1
101     1       1
10      11      0
1       110     1
0       1101    n/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.
• ###### 9. Re: How to reverse bits (big endian to little endian)?
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.