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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.