JOIN
Get Time

Member Search

SEARCH
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Forums Tutorial Discussions A bit of fun: fun with bits Fastest way to reverse bits
Fastest way to reverse bits | Reply

gsais
808 posts
Does anyone knows which is the fastest way (in x86 computers) to reverse the bits of 32-bit integer? (assembler is ok)

For example, reversing:
11000110001000000111001011000001

would yield:
10000011010011100000010001100011
Re: Fastest way to reverse bits (response to post by gsais) | Reply
darko_aleksic
1030 posts
I don't, but maybe this will help:
http://graphics.stanford.edu/~seander/bithacks.html

See also "Hacker's Delight", Ch.7
Re: Fastest way to reverse bits (response to post by darko_aleksic) | Reply

gsais
808 posts
Thanks, I found the answer on the link you provided (I don't know if it's the fastest way, but at least it must be very close to the optimal):

Reverse an N-bit quantity in parallel in 5 * lg(N) operations:
unsigned int v; // 32 bit word to reverse bit order
 
// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);
Re: Fastest way to reverse bits (response to post by gsais) | Reply
darko_aleksic
1030 posts
Well, here's the code from "Hacker's Delight" (Warren, Addison/Wesley 2003) - I guess it amounts to the same thing:
unsigned rev(unsigned x){
    x = (x & 0x55555555) << 1 | (x >> 1) & 0x55555555;
    x = (x & 0x33333333) << 2 | (x >> 2) & 0x33333333;
    x = (x & 0x0F0F0F0F) << 4 | (x >> 4) & 0x0F0F0F0F;
    x = (x << 24) | ((x & 0xFF00) << 8) |
        ((x >> 8) & 0xFF00) | (x >> 24);
    return x;
}


[EDIT] Note that if you use Java, you want to use unsigned right shift (>>>)
Re: Fastest way to reverse bits (response to post by darko_aleksic) | Reply

gsais
808 posts
They seem to be similar, but when I compared both techniques (in C++), the first one (from the "bithacks" page) is about 50% faster than the second (from "Hacker's Delight"). That's on an AMD Athlon 64 3000+, using gcc 3.4.4 (from cygwin) with -O3 enabled.
Re: Fastest way to reverse bits (response to post by gsais) | Reply
darko_aleksic
1030 posts
Interesting... in "Hacker's Delight" they start with almost the same code and then they say "A small improvement results on most machines by using fewer distinct large constants and [emphasis mine] doing the last two assignments in a more straightforward way..."
... and then they end up with the code above. I guess improvements and "improvements" are not the same thing :)
Re: Fastest way to reverse bits (response to post by gsais) | Reply
wongiseng
369 posts
OOT: I think since you focus on performance and you're not using java, this library is out of the question right ? :)

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Integer.html#reverse(int)
Forums Tutorial Discussions A bit of fun: fun with bits Fastest way to reverse bits
Previous Thread  |  Next Thread 		RSS