Bit Twiddling Hacks
bit-manipulationc-programmingperformancelow-level
Abstraction: Reference collection of low-level C bit manipulation tricks
Key points:
- Sign detection via arithmetic right-shift:
sign = v >> (sizeof(int)*CHAR_BIT - 1)produces -1 or 0; ANSI C does not guarantee behavior on signed right-shift so portability varies. - Branchless min/max via XOR:
r = y ^ ((x ^ y) & -(x < y))avoids branch mispredictions on certain CPUs. - Kernighan's bit-count method
v &= v - 1(clear lowest set bit) iterates only as many times as bits are set; the parallel population-count method requires 12 operations for 32-bit integers. - Power-of-2 test:
(v & (v - 1)) == 0(withv && ...to exclude 0). - Bit reversal of a byte in 3 multiply-and-mask operations using magic constants (e.g.,
(b * 0x0202020202ULL & 0x010884422010ULL) % 1023). - DeBruijn sequence multiply-and-lookup computes integer log2 in 13 operations with a 32-entry table.
Connections: Stanford · Bit Manipulation · Low Level Programming · Performance Optimization
Source: http://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign