Bit Manipulation Tricks

// Check if bit i is set:     (x >> i) & 1
// Set bit i:                 x |= (1 << i)
// Clear bit i:               x &= ~(1 << i)
// Toggle bit i:              x ^= (1 << i)
// Least significant set bit: x & -x
// Remove LSB:                x & (x - 1)
// Count set bits:            __builtin_popcount(x) (C++)
// Count set bits:            x.count_ones() (Rust)

// Check if power of two:
bool is_pow2(int x) { return x > 0 && !(x & (x - 1)); }

// Get the lowest set bit:
int lsb(int x) { return x & -x; }

// Enumerate subsets of a bitmask:
for (int sub = mask; sub; sub = (sub - 1) & mask) { }