[Nottingham] A Little Coding Gem

[Duncan]

On 15/11/12 18:08, Martin wrote:
> Folks,
> 
> Fortune has just served up a little beauty for me just now:
> 
> 
>    n = ((n >>  1) & 0x55555555) | ((n <<  1) & 0xaaaaaaaa);
>    n = ((n >>  2) & 0x33333333) | ((n <<  2) & 0xcccccccc);
>    n = ((n >>  4) & 0x0f0f0f0f) | ((n <<  4) & 0xf0f0f0f0);
>    n = ((n >>  8) & 0x00ff00ff) | ((n <<  8) & 0xff00ff00);
>    n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
> 
> -- Yet another mystical 'C' gem. ...
> 
> 
> Anyone like to guess or even work out what it does? :-> (Evil grin :-) )
> 
The wrong thing if n isn't a 32 bit int.  And guess what 'int's are
not guaranteed to be in C :)

For a 32 bit int it reverses the order of the bits by
swapping larger and larger chunks (see below).

> More to the point, why would you want to do that?!
> 
Because it mostly uses fast bitwise operators which most CPU will
do in a single instruction, uses a single variable and because
it takes fewer operations than there are bits, or simply because
 you can.

Have fun,
Duncan

The magic sauce in action:
START n = abcdefghijklmnopqestuvwxyzABCDEF

n = ((abcdefghijklmnopqestuvwxyzABCDEF >> 1) & 01010101010101010101010101010101)
| ((abcdefghijklmnopqestuvwxyzABCDEF << 1) & 10101010101010101010101010101010)

= (0abcdefghijklmnopqestuvwxyzABCDE & 01010101010101010101010101010101)
| (bcdefghijklmnopqestuvwxyzABCDEF0 & 10101010101010101010101010101010)

=   0a0c0e0g0i0k0m0o0q0s0u0w0y0A0C0E
|   b0d0f0h0j0l0n0p0r0t0v0x0z0B0D0F0
=   badcfehgjilknmporqtsvuxwzyBADCFE


n = (badcfehgjilknmporqtsvuxwzyBADCFE >> 2) & 00110011001100110011001100110011)
| (badcfehgjilknmporqtsvuxwzyBADCFE << 2) & 11001100110011001100110011001100)

= ( 00badcfehgjilknmporqtsvuxwzyBADC & 00110011001100110011001100110011 )
| ( dcfehgjilknmporqtsvuxwzyBADCFE00 & 11001100110011001100110011001100 )

=   00ba00fe00ji00nm00rq00vu00zy00DC
=   dc00hg00lk00po00ts00xw00BA00FE00
=   dcbahgfelkjiponmtsrqxwvuBAzyFEDC


n = ((dcbahgfelkjiponmtsrqxwvuBAzyFEDC >> 4) & 00001111000011110000111100001111)
| ((dcbahgfelkjiponmtsrqxwvuBAzyFEDC << 4) & 11110000111100001111000011110000)

= 0000dcbahgfelkjiponmtsrqxwvuBAzy & 00001111000011110000111100001111
| hgfelkjiponmtsrqxwvuBAzyFEDC0000 & 11110000111100001111000011110000

= 0000dcba0000lkji0000tsrq0000BAzy
| hgfe0000ponm0000xwvu0000FEDC0000

= hgfedcbaponmlkjixwvutsrqFEDCBAzy


n = ((hgfedcbaponmlkjixwvutsrqFEDCBAzy >> 8) & 00000000111111110000000011111111)
| ((hgfedcbaponmlkjixwvutsrqFEDCBAzy << 8) & 11111111000000001111111100000000)

= 00000000hgfedcbaponmlkjixwvutsrq & 00000000111111110000000011111111
| ponmlkjixwvutsrqFEDCBAzy00000000 & 11111111000000001111111100000000

= 00000000hgfedcba00000000xwvutsrq
| ponmlkji00000000FEDCBAzy00000000

= ponmlkjihgfedcbaFEDCBAzyxwvutsrq


n = ((ponmlkjihjgedcbaFEDCBAzyxwvutsrq >> 16) & 00000000000000001111111111111111)
| ((ponmlkjihgfedcbaFEDCBAzyxwvutsrq << 16) & 11111111111111110000000000000000)

= 0000000000000000ponmlkjihgfedcba & 00000000000000001111111111111111
  FEDCBAzyxwvutsrq0000000000000000 & 00000000000000000000111110100110

= 0000000000000000ponmlkjihgfedcba
| FEDCBAzyxwvutsrq0000000000000000

= FEDCBAzyxwvutsrqponmlkjihgfedcba

QED.