Editor's note:
COTD Entry: Power of 2 bitmasking tricks by Andy Younger [andyy@redlemon.com]
/*
* Here are a few nice tricks for 2's complement based machines
* that I discovered a few months ago.
*/
inline int LowestBitMask(int v)
{
return ((v & -v));
}
/* Confusing? A simpler version (not relying on 2's complement) is below
*
* If you don't understand what is going on, work it out on paper with the bitmasks
*/
inline int LowestBitMask_No2sComplement(int v)
{
return (v & ((~v)+1));
}
/* Ok, so now we are cooking on gass. Here we use this function for some */
/* rather useful utility functions */
inline bool IsPow2(int v)
{
return (LowestBitMask(v) == v) ? true : false;
}
inline int CeilPow2(int v)
{
int i = LowestBitMask(v);
while(i < v)
i <<= 1;
return i;
}
/* Here is some test code, to check the above works */
/* This tested with Cygwin's gcc & VC6 */
#include <stdio.h>
#include <assert.h>
int main()
{
assert( IsPow2(128) );
assert( !IsPow2(15) );
assert( CeilPow2(0x200) == 0x200 );
assert( CeilPow2(0x201) == 0x400 );
assert( CeilPow2(0x3ff) == 0x400 );
assert( CeilPow2(0x400) == 0x400 );
assert( CeilPow2(0x401) == 0x800 );
return 0;
}
/* END! */ |