Bit Twiddling Hacks

Abstraction: Low-level C bit manipulation tricks for performance-critical integer operations

Key points:

• Sign detection, absolute value, min/max without branching using arithmetic right-shift and XOR masks
• Bit counting (popcount): naive O(bits), Kernighan's O(set-bits), parallel 12-operation method using magic constants, 64-bit multiply+modulo method for up to 32 bits
• Bit reversal: table lookup (12 ops), parallel swap of pairs/nibbles/bytes (O(log N))
• Log base 2: floating-point exponent trick, 256-entry table (7 ops), De Bruijn multiply+lookup (13 ops)
• Modulus by power-of-2 minus 1 (e.g., d=7,15,31...) in O(lg N) using precomputed tables
• XOR swap and merge bits under a mask are classic O(1) tricks without temporary variables

Connections: Stanford University · Bit Manipulation · Low Level Programming · Algorithm Optimization

Source: http://graphics.stanford.edu/~seander/bithacks.html