Reverse bit order in a byte

Posted on 2006-06-07
Last Modified: 2010-05-18

I need some VERY efficient code to reverse the bit order in a byte.
I found a thread in this forum about it, but I can't quickly determine what is the best way to go.

Can someone give me a complete piece of code that will do the job?

Question by:JohnRobottom
    LVL 23

    Accepted Solution

    My first attempt would be a table lookup:

    unsigned char reverse[255] = { 0x00, 0x80, 0x40, 0xC0, ... };

    LVL 5

    Expert Comment

    i think you can use the left shift and right shift operators that's efficient enough.

    If not, use Assembly code.. but then that makes your code processor specific..
    LVL 5

    Expert Comment


    Please check this link..

    looks good to me..

    LVL 14

    Expert Comment

    I agree with brettmjohnson to use a table lookup.

    but you should not calculate the whole table yourself, just write a program which generates the table.
    LVL 5

    Expert Comment

    someone already took the pains :-)

    const unsigned char BitReverseTable256[] =
      0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
      0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
      0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
      0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
      0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
      0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
      0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
      0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
      0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
      0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
      0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
      0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
      0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
      0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
      0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
      0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF

    unsigned int v; // reverse 32-bit value, 8 bits at time
    unsigned int c; // c will get v reversed

    // Option 1:
    c = (BitReverseTable256[v & 0xff] << 24) |
        (BitReverseTable256[(v >> 8) & 0xff] << 16) |
        (BitReverseTable256[(v >> 16) & 0xff] << 8) |
        (BitReverseTable256[(v >> 24) & 0xff]);

    // Option 2:
    unsigned char * p = (unsigned char *) &v;
    unsigned char * q = (unsigned char *) &c;
    q[3] = BitReverseTable256[p[0]];
    q[2] = BitReverseTable256[p[1]];
    q[1] = BitReverseTable256[p[2]];
    q[0] = BitReverseTable256[p[3]];

    The first method takes about 17 operations, and the second takes about 12, assuming your CPU can load and store bytes easily.

    heh heh..

    LVL 22

    Assisted Solution

    Are you preparing data for a FFT?

    In that case I'd look at some canned FFT library.  These often have really speedy bit-reversing code, optimized to use the SIMD instructions.  Many times faster than anything you can cook up in C.

    The Intel lmath library comes to mind.

    LVL 45

    Expert Comment

    Hi JohnRobottom,

    We had this question just a short while ago.  Check the conversation at this link:

    The bottom line is that this short function is very efficient, especially if you declare it as "inline".

    unsigned ReverseBits (unsigned char Source)
      unsigned Result;

      Result = (Source >> 4) | (Source << 4);
      Result = ((Result & 0xcc) >> 2 ) | ((Result & 0x33) << 2);
      Result = ((Result & 0xaa) >> 1 ) | ((Result & 0x55) << 1);
      return Result;

    Good Luck!
    LVL 8

    Expert Comment

    function RevByte(const X : byte) : byte ;
    type BS = set of 0..7 ;
    var K : byte ; Q : BS ;
    begin Q := [] ;
      for K := 0 to 7 do if 7-K in BS(X) then Include(Q, K) ;
      RevByte := byte(Q) end ;

    function ByteRev(X : byte) : byte ;
    var K : byte ; Q : byte ;
    begin Q := 0 ;
      for K := 0 to 7 do begin Q := 2*Q + Ord(Odd(X)) ;
        X := X div 2 end ;
      ByteRev := Q end ;

    chk if it works for u..
    LVL 45

    Expert Comment

    Hi kaliyugkaarjun,

    This is a C forum.  Pascal code usually isn't much help here.

    But thanks for posting!

    Expert Comment

    Hi JohnRobottom,

          You can use the following piece of code to reverse bits in a byte. If x is an integer whose bits have to be reversed then,
          int x,y;
          y = [ ((x & 1) << 7) | ((x & 2) << 5) | ((x & 4) << 3) | ((x & 8) << 1) | ((x & 16) >> 1) | ((x & 32) >> 3) | ((x & 64) >> 5) | ((x & 128) >> 7) ]

             with regards,

    Featured Post

    Maximize Your Threat Intelligence Reporting

    Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

    Join & Write a Comment

    Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
    Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
    The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
    The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

    729 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now