Skip to content

Bit Representation & Sets as Bits

Integers as bit vectors pack many boolean flags into one machine word. In competitive programming, subset of \(\{0,\ldots,n-1\}\) is often uint32_t or uint64_t with bit i meaning “element \(i\) is included.”

Core operations

For a mask m and index i (0-based):

Intent Expression
Test if \(i\) in set (m >> i) & 1 or (m >> i) & 1u
Set bit \(i\) m \| (1u << i)
Clear bit \(i\) m & ~(1u << i)
Flip bit \(i\) m ^ (1u << i)
Lowest set bit m & -m (two’s complement; signed pitfalls—prefer unsigned)
Remove lowest set bit m & (m - 1) 
#include <cstdint>

bool hasBit(uint32_t m, int i) { return (m >> i) & 1u; }

uint32_t setBit(uint32_t m, int i) { return m | (1u << i); }

uint32_t clearBit(uint32_t m, int i) { return m & ~(1u << i); }

int popcount(uint32_t m) { return __builtin_popcount(m); } // GCC/Clang

int lowestBitIndex(uint32_t m) { return __builtin_ctz(m); } // undefined if m==0

Use unsigned types for shifts to avoid undefined behavior with negative or oversized shifts.

Iterating subsets

All non-empty submasks of m:

for (uint32_t s = m; s; s = (s - 1) & m) {
    // s runs over all submasks of m
}

All k-element subsets of n bits: combine with combinatorial generation or use when \(n\) is small.

Signed vs unsigned

Right shift of signed negative values is implementation-defined for >> in older C++ for negatives; for bit tricks prefer uint32_t / uint64_t.