[math-fun] reversing the order of bits in a word

Let w be a 64-bit word ("unsigned long long," in C language). The following C instruction sequence w ^= w>>32; w ^= w<<32; w ^= w>>32; w ^= w>>16; w ^= w<<16; w ^= w>>16; w ^= w>>8; w ^= w<<8; w ^= w>>8; w ^= w>>4; w ^= w<<4; w ^= w>>4; w ^= w>>2; w ^= w<<2; w ^= w>>2; w ^= w>>1; w ^= w<<1; w ^= w>>1; will overwrite w with its bit-order-reversal. In general for a (2^k)-bit long word this will use 3*k shifts and 3*k XOR operations and with zero(?) or one(?) extra registers consumed for temp storage and no funny masking constants needed. -- Warren D. Smith http://RangeVoting.org