← All patterns

Bitwise Operations

Each bit is a flag or part of an integer encoding. XOR cancels pairs, AND masks, popcount counts set bits. Subset masks, parity tricks, position toggles, and arithmetic without operators.

17 problems 8 Easy 6 Medium 3 Hard

Bits as flags or as digits in a base-2 number. XOR cancels paired values; AND masks subsets; OR accumulates. Subset enumeration with bitmask `0..(1<<n)-1`; popcount counts set bits; `x & -x` isolates the lowest set bit. Useful for set-cover, parity tricks, TSP-style DP, and arithmetic without arithmetic operators.

Most problems either use bits as set membership (subset DP) or as integer encoding (single-number, hamming distance).

When to reach for this pattern

  • Find the unique value among duplicates (XOR cancels pairs)
  • Subset enumeration with small n (≤ 20)
  • Bit-counting, popcount, parity
  • Arithmetic without arithmetic operators (sum-of-two-integers)

Canonical template 

// enumerate all 2^n subsets
for (int mask = 0; mask < (1 << n); ++mask) {
    for (int i = 0; i < n; ++i) if (mask >> i & 1) {
        // i-th element is in the subset
    }
}

// useful bit tricks
int lsb = mask & -mask;            // lowest set bit
int cleared = mask & (mask - 1);   // clear lowest set bit
int popcount = __builtin_popcount(mask);

C++ · adapt the names and types to your problem.

Common pitfalls

  • 1 << k is a signed int by default in C++ — use 1LL << k for k >= 31
  • XOR sums require care with long long for large counts
  • Subset DP iteration order: process masks in increasing size for forward DP
  • Hardware-specific intrinsics (__builtin_popcount) — portability requires guards

Related patterns

Subsets Dynamic Programming

Problems (17)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.