[Nottingham] A Little Coding Gem

[Martin]

On 15/11/12 21:39, Duncan 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);

Hey! Good stuff all round.

Yep, that reverses the bits in a 32-bit int.

And yep, you need to be sure of how many bits there are in whatever
variable type you are using or have defined.


Two aspects that caught my eye are that:

It uses binary powers in a similar way to how quick-sort uses binary
chop to analogously 'sort' the bits into the correct order;

And you should be able to do that using just two CPU registers to make
it all nice and fast.


As to *why* you might want that... Well, I can't think of a case other
than for reverse sorting an int shift register of boolean flags of some
event for whatever reason.

We have a mix of "big endian" and "little endian" systems, however that
is of little concern being as whatever endian-ness is untangled at
whatever communications or storage interface is used.

So... What would that usefully be used for?...


Thanks to Mike for the demo test code and to Duncan for the excellent
dry run.

Any other goodies of note?

Cheers,
Martin




-- 
- ------------------ - ----------------------------------------
-    Martin Lomas    - OpenPGP (GPG/PGP) Public Key: 0xCEE1D3B7
- martin @ ml1 co uk - Import from   hkp://subkeys.pgp.net   or
- ------------------ - http:// ml1 .co .uk/martin_ml1_co_uk.gpg