What is the fastest way to do a bit-reversal?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

What is the fastest way to do a bit-reversal?

Post by little joey » Tue Oct 11, 2005 8:30 pm

Hi All,

I like to do a bit-reversal on unsigned 32-bit integers; that is, if the original number in binary is f.i. 0111.0010.1111.0010.0001.1100.0101.1011, then the bit-reversal would be 1101.1010.0011.1000.0100.1111.0100.1110 (dots are for clarity). The naive algorithm would take 32 iterations in a loop and could look something like this (in C):

Code: Select all

unsigned bitreverse(unsigned n){
   unsigned himask=1<<31;
   unsigned lomask=1;
   unsigned result=0;
   int i;
   
   for(i=0;i<32;i++){
      if(n&lomask) result|=himask;
      lomask<<=1;
      himask>>=1;
      }
   return result;
   }
But I want to do it as fast as possible because in the program I would call function bitreverse() millions of times. Are there inherently faster algorithms for this operation? Mathematical tricks (no matter how dirty)? I thought about lookup tables, but I want to keep it as small as possible.

Ideas are welcome.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Oct 12, 2005 1:58 am

Is a table of size 65536 too large for you?

Code: Select all

unsigned int r16[65536];
// preprocess r16 to be the bit-reverse of all 16-bit integers
// then, y will be the 32-bit reverse of x:
y = (r16[x & 0xffff] << 16) | (r16[x >> 16]);
It can be change to 8-bit table if 65536 is too large.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Oct 12, 2005 8:22 am

That is probably the best way to do it. Alternatively I can use an 8-bit lookup table four times which uses less memory and about double the time.
But I still like to know if there a re fast ways without lookup tables.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Oct 12, 2005 10:04 am

Some more ways to do it can be found http://graphics.stanford.edu/~seander/bithacks.html , always a nice reference for bit fiddling stuff.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Oct 12, 2005 11:39 am

That is a most useful link. I immediately added it to my bookmarks.
Thanks!

Post Reply

Return to “Algorithms”