To do it in O(1) for N bits, you need a table lookup. But for 32 bits, the
table is 16 Gb. A compromise is to build a table of 256 entries to reverse
the bits in a byte (it's easy to write a program to do this). Then the
result is something like
unsigned reverse_bits(unsigned x)
{
static unsigned rev[] = { 0x00, 0x80, ... };
return (((rev[x & 0xff] << 8) | (rev[(x >> 8) & 0xff] << 8)) |
(rev[(x >> 16) & 0xff]) << 8)) | (rev(x >> 24] << 8);
}
Google "reverse bits" and you will get dozens of algorithms to do the same
thing. This one is a
favorite http://graphics.stanford.edu/~seander/bithacks.html
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/YdEV-io9poQJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
