[Nottingham] A Little Coding Gem

[Camilo Mesias]

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...

-Cam
On Nov 15, 2012 9:39 PM, "Duncan" <notlug at pendinas.org.uk> wrote:

> 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.
>
>
> _______________________________________________
> Nottingham mailing list
> Nottingham at mailman.lug.org.uk
> https://mailman.lug.org.uk/mailman/listinfo/nottingham
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.lug.org.uk/pipermail/nottingham/attachments/20121115/460994b2/attachment-0001.html>