------------------------------------------------------------------------------- Small mystical Bit Programming Algorithms ------------------------------------------------------------------------------- To find the smallest 1 bit in a word EG:- ~~~~~~10---0 => 0----010---0 #define LowestOneBit(w) ((w) & (~(w)+1)) or #define LowestOneBit(w) ((w) & (-(w))) Determine if one of the bytes in a 4 byte word is zero if ( ( x + 0xfefefeff ) & (~x) & 0x80808080 ) { ... } Reverse the bits in a word. (each line can be done in any order. 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); Etc for larger intergers (64 bits in Java) NOTE: the >> operation must be unsigned! (EG the >>> operator in java) Swap two intergers without any extra space #define SWAP(a,b) { a ^= b; b ^= a; a ^= b; } Count the number of bits in a bitfield This relies of the fact that the count of n bits can NOT overflow an n bit interger. EG: 1 bit count takes a 1 bit interger, 2 bit counts 2 bit interger, 3 bit count requires only a 2 bit interger. So we add all bit pairs, then each nible, then each byte etc... 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); Etc for larger intergers (64 bits in Java) NOTE: the >> operation must be unsigned! (>>> in java) Spread out bits. EG 00001111 -> 0101010101 00001010 -> 0100010000 This is used to interleve to intergers to produce a `Morten Key' used in Space Filling Curves (See DrDobbs Journal, July 1999) Order is important, below is designed for 64 bit numbers . n = ( n & 0x000000000000ffffL) | (( n & 0x00000000ffff0000L) << 16); n = ( n & 0x000000ff000000ffL) | (( n & 0x0000ff000000ff00L) << 8); n = ( n & 0x000f000f000f000fL) | (( n & 0x00f000f000f000f0L) << 4); n = ( n & 0x0303030303030303L) | (( n & 0x0c0c0c0c0c0c0c0cL) << 2); n = ( n & 0x1111111111111111L) | (( n & 0x2222222222222222L) << 1);