Reverse bit order in a byte

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..

Hi,

Please check this link..

http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

looks good to me..

Regards,
Siddhesh

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.

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..

Regards,
Siddhesh

Hi JohnRobottom,

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

  https://www.experts-exchange.com/questions/21865419/Reverse-bits-in-a-byte.html


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!
Kent

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..

Hi kaliyugkaarjun,

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

But thanks for posting!
Kent

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,
        Vinay