JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Fastest way to reverse bits | Reply
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
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
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
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
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
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
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)
RSS