<p>Back in the days of 8-bit micros the fastest way I could find to do that was a look-up table. I wonder if modern CPUs with fancy caches and pipelined architecture could go fastest that way or using the code snippet above... </p>

<p>-Cam</p>
<div class="gmail_quote">On Nov 15, 2012 9:39 PM, "Duncan" <<a href="mailto:notlug@pendinas.org.uk">notlug@pendinas.org.uk</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 15/11/12 18:08, Martin wrote:<br>
> Folks,<br>
><br>
> Fortune has just served up a little beauty for me just now:<br>
><br>
><br>
>    n = ((n >>  1) & 0x55555555) | ((n <<  1) & 0xaaaaaaaa);<br>
>    n = ((n >>  2) & 0x33333333) | ((n <<  2) & 0xcccccccc);<br>
>    n = ((n >>  4) & 0x0f0f0f0f) | ((n <<  4) & 0xf0f0f0f0);<br>
>    n = ((n >>  8) & 0x00ff00ff) | ((n <<  8) & 0xff00ff00);<br>
>    n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);<br>
><br>
> -- Yet another mystical 'C' gem. ...<br>
><br>
><br>
> Anyone like to guess or even work out what it does? :-> (Evil grin :-) )<br>
><br>
The wrong thing if n isn't a 32 bit int.  And guess what 'int's are<br>
not guaranteed to be in C :)<br>
<br>
For a 32 bit int it reverses the order of the bits by<br>
swapping larger and larger chunks (see below).<br>
<br>
> More to the point, why would you want to do that?!<br>
><br>
Because it mostly uses fast bitwise operators which most CPU will<br>
do in a single instruction, uses a single variable and because<br>
it takes fewer operations than there are bits, or simply because<br>
 you can.<br>
<br>
Have fun,<br>
Duncan<br>
<br>
The magic sauce in action:<br>
START n = abcdefghijklmnopqestuvwxyzABCDEF<br>
<br>
n = ((abcdefghijklmnopqestuvwxyzABCDEF >> 1) & 01010101010101010101010101010101)<br>
| ((abcdefghijklmnopqestuvwxyzABCDEF << 1) & 10101010101010101010101010101010)<br>
<br>
= (0abcdefghijklmnopqestuvwxyzABCDE & 01010101010101010101010101010101)<br>
| (bcdefghijklmnopqestuvwxyzABCDEF0 & 10101010101010101010101010101010)<br>
<br>
=   0a0c0e0g0i0k0m0o0q0s0u0w0y0A0C0E<br>
|   b0d0f0h0j0l0n0p0r0t0v0x0z0B0D0F0<br>
=   badcfehgjilknmporqtsvuxwzyBADCFE<br>
<br>
<br>
n = (badcfehgjilknmporqtsvuxwzyBADCFE >> 2) & 00110011001100110011001100110011)<br>
| (badcfehgjilknmporqtsvuxwzyBADCFE << 2) & 11001100110011001100110011001100)<br>
<br>
= ( 00badcfehgjilknmporqtsvuxwzyBADC & 00110011001100110011001100110011 )<br>
| ( dcfehgjilknmporqtsvuxwzyBADCFE00 & 11001100110011001100110011001100 )<br>
<br>
=   00ba00fe00ji00nm00rq00vu00zy00DC<br>
=   dc00hg00lk00po00ts00xw00BA00FE00<br>
=   dcbahgfelkjiponmtsrqxwvuBAzyFEDC<br>
<br>
<br>
n = ((dcbahgfelkjiponmtsrqxwvuBAzyFEDC >> 4) & 00001111000011110000111100001111)<br>
| ((dcbahgfelkjiponmtsrqxwvuBAzyFEDC << 4) & 11110000111100001111000011110000)<br>
<br>
= 0000dcbahgfelkjiponmtsrqxwvuBAzy & 00001111000011110000111100001111<br>
| hgfelkjiponmtsrqxwvuBAzyFEDC0000 & 11110000111100001111000011110000<br>
<br>
= 0000dcba0000lkji0000tsrq0000BAzy<br>
| hgfe0000ponm0000xwvu0000FEDC0000<br>
<br>
= hgfedcbaponmlkjixwvutsrqFEDCBAzy<br>
<br>
<br>
n = ((hgfedcbaponmlkjixwvutsrqFEDCBAzy >> 8) & 00000000111111110000000011111111)<br>
| ((hgfedcbaponmlkjixwvutsrqFEDCBAzy << 8) & 11111111000000001111111100000000)<br>
<br>
= 00000000hgfedcbaponmlkjixwvutsrq & 00000000111111110000000011111111<br>
| ponmlkjixwvutsrqFEDCBAzy00000000 & 11111111000000001111111100000000<br>
<br>
= 00000000hgfedcba00000000xwvutsrq<br>
| ponmlkji00000000FEDCBAzy00000000<br>
<br>
= ponmlkjihgfedcbaFEDCBAzyxwvutsrq<br>
<br>
<br>
n = ((ponmlkjihjgedcbaFEDCBAzyxwvutsrq >> 16) & 00000000000000001111111111111111)<br>
| ((ponmlkjihgfedcbaFEDCBAzyxwvutsrq << 16) & 11111111111111110000000000000000)<br>
<br>
= 0000000000000000ponmlkjihgfedcba & 00000000000000001111111111111111<br>
  FEDCBAzyxwvutsrq0000000000000000 & 00000000000000000000111110100110<br>
<br>
= 0000000000000000ponmlkjihgfedcba<br>
| FEDCBAzyxwvutsrq0000000000000000<br>
<br>
= FEDCBAzyxwvutsrqponmlkjihgfedcba<br>
<br>
QED.<br>
<br>
<br>
_______________________________________________<br>
Nottingham mailing list<br>
<a href="mailto:Nottingham@mailman.lug.org.uk">Nottingham@mailman.lug.org.uk</a><br>
<a href="https://mailman.lug.org.uk/mailman/listinfo/nottingham" target="_blank">https://mailman.lug.org.uk/mailman/listinfo/nottingham</a><br>
</blockquote></div>