Cute Code Tricks
(Reproduced from http://www.sjbaker.org/wiki/index.php?title=Cool_Code_list as a backup)
Here is my collection of cute C and C++ tricks - I have tried to stick with code that is actually faster or more compact than the conventional way of doing things - or maybe the code just has to look pretty on the page - but this a personal collection, so I get to break the rules if I feel like it!
Unless I indicate otherwise, all variables are unsigned 32 bit integers.
The code snippets on this page are hereby placed into the public domain - they are free for any use whatever. (And in any case, you'll find these tricks out there 'in the wild' in hundreds of programs under dozens of licenses!) SteveBaker 14:25, 13 December 2008 (PST)
Reverse all the bits in a 32 bit word
I found this one in the Linux fortune cookie program (!)
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) ;
You can easily make versions of this for other word sizes.
Count the number of '1' bits in a 32 bit word
John C. Wren kindly sent me this one. It looks amazingly similar to the previous trick for bit reversal.
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1); n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2); n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4); n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8); n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);
Test to see if a number is an exact power of two
b = ((n&(n-1))==0) ;
(NB: This code sets 'b' to TRUE if 'n' is an integer power of two - in this context, both zero and one are considered to be powers of two.)
This code actually works by changing the least significant '1' bit of 'n' to a '0'. If 'n' is a power of two, it only has one '1' bit - and zeroing it leaves you with zero as the answer.
Hence, the inner expression is also a cute trick...
Zero the least significant '1' bit in a word.
n&(n-1)
Set the least significant N bits in a word.
~(~0<<n)
Swap the values of two integers.
This one is cute because it doesn't use a temporary variable and it's harder to get wrong than the usual code. It's been around for years, so I have no idea who invented it.
x = x ^ y ; y = x ^ y ; x = x ^ y ;
(The '^' operator stand for 'bitwise XOR' in C/C++ - not 'to the power of' as ex-FORTRAN people seem to think!)
However Scott Smith pointed out that this is equivelent to the even more aesthetically pleasing:
x ^= y ^= x ^= y ;
It has been pointed out that this is strictly illegal C++ since the same variable is modified twice in one statement.
Convert a nibble into an ASCII hex digit.
Another ancient one. I think I first saw it in the sources for 'vi', but it's probably a lot older than that.
"0123456789ABCDEF" [ n ]
(Where 'n' is in the range 0..15).
I have also seen this:
n [ "0123456789ABCDEF" ]
...which also works providing 'n' is a character variable and providing you turn off enough compiler error checking!
Force all non-zero values to 1.
Pat Down sent me this one:
b = !!a ;
b = 0 if a was 0 otherwise b = 1.
Little-Endian or Big-Endian?
Some computers store integers with the most significant data in the first byte and the least significant data in the last, others do it the other way around. The former type are called 'big-endian' and the latter 'little-endian'. Intel computers are traditionally little-endian and most others big-endian.
Most people do not realise that the terms 'big-endian' and 'little-endian' come from Gulliver's Travels. The nations of Lilliput and Blefuscu were waging a terrible and bloody war over which end one should cut open on a boiled egg - the little end or the big end.
The war between CPU manufacturers is just as silly - and also pretty damaging.
Gulliver says: "...all true Believers shall break their Eggs at the convenient End: and which is the convenient End, seems, in my humble Opinion, to be left to every Man's Conscience, or at least in the power of the Chief Magistrate to determine."
Hmmmm.
Anyway, the way to decide which kind of machine you have is:
int i = 1 ; little_endian = *((char *) &i ) ;
Duffs Device
No collection would be complete without this:
int a = some_number ;
int n = ( a + 4 ) / 5 ;
switch ( a % 5 )
{
case 0: do
{
putchar ( '*' ) ;
case 4: putchar ( '*' ) ;
case 3: putchar ( '*' ) ;
case 2: putchar ( '*' ) ;
case 1: putchar ( '*' ) ;
} while ( --n ) ;
}
printf ( "\n" ) ;
The loop prints the 'a' asterisks - but is 'unrolled' (which is important for speed in some applications). Most people are suprised that this even compiles.
It has been said that the worst problem with Duff's device is knowing how to indent it!
If you have any more good examples for my collection, you can email me at: steve@sjbaker.org.
