• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2812
  • Last Modified:

Reverse bit order in a byte

Hi,

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?

Thanks!

jrobotto@nortel.com
0
JohnRobottom
Asked:
JohnRobottom
2 Solutions
 
brettmjohnsonCommented:
My first attempt would be a table lookup:

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

0
 
cryptosidCommented:
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..
0
 
cryptosidCommented:
Hi,

Please check this link..

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

looks good to me..

Regards,
Siddhesh
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
cwwkieCommented:
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.
0
 
cryptosidCommented:
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
0
 
grg99Commented:
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.



0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi JohnRobottom,

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

  http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_21865419.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
0
 
kaliyugkaarjunCommented:
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..
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi kaliyugkaarjun,

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

But thanks for posting!
Kent
0
 
Vinay_GRCommented:
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
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now