JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design 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 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: 11000110001000000111001011000001would 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.htmlSee 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)
 Forums Tutorial Discussions A bit of fun: fun with bits Fastest way to reverse bits Previous Thread  |  Next Thread