9 Replies Latest reply: Jul 27, 2007 3:56 PM by baftos RSS

    How to reverse bits (big endian to little endian)?

    800306
      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)?
          807605
          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)?
            baftos
            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)?
              796365
              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)?
                800306
                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)?
                  baftos
                  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)?
                    796365
                    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)?
                      807605
                      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)?
                        807605
                        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)?
                          baftos
                          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.