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

28 Mar 2014


      Nice. I've never seen it before. (In particular, it's not in
Hacker's Delight.)

On Fri, 28 Mar 2014, Warren D Smith wrote:
...
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.
-- 
Tom Duff.  We can give no comment on this as it is too scientific.