λDSA Learning Hubpart of DSA Atlas

Bit Manipulation

Advanced~2h · 6 lessons10 practice problems

Integers as arrays of bits: AND/OR/XOR/shifts, the classic tricks (clear lowest set bit, XOR to cancel pairs), bitmasks, and O(1) set operations.

0 of 6 lessons checked off

Introduction

What it is

  • Bit manipulation treats an integer as a fixed array of binary digits and operates on them directly with bitwise operators: AND (&), OR (|), XOR (^), NOT (~), and shifts (<<, >>).
  • It enables O(1) tricks — check/set/clear a bit, count set bits, use an integer as a compact set (bitmask) — that would otherwise need loops or extra structures.

Why it matters

  • Some problems have elegant bit-based O(n)/O(1) solutions that are near-impossible otherwise: 'find the single number among pairs' via XOR, subset enumeration via bitmasks, and state compression in DP.
  • It's also a systems/embedded staple, and interviewers use it to probe comfort with the machine-level view of data.

How it works

  • Each operator acts bit-by-bit: AND masks bits off, OR sets them, XOR flips/cancels, shifts multiply/divide by powers of two.
  • Key identities: x ^ x = 0 and x ^ 0 = x (XOR cancels pairs); n & (n−1) clears the lowest set bit; 1 << k is a mask for bit k.
  • A bitmask is an integer whose bits represent set membership: bit i set means element i is in the set — enabling O(1) union (|), intersection (&), and toggle (^).

Where it's used

  • Permission/feature flags (read/write/execute bits), network subnet masks, compression, hash functions, graphics color channels, and bitmask DP for the Traveling Salesman problem.

In interviews

  • Single number, number of 1 bits (Hamming weight), counting bits, power of two, missing number, subsets via bitmask, maximum XOR (with tries), reverse bits.
Analogy: A row of light switches, one per bit. AND keeps only switches on in both rows; OR turns on any that's on in either; XOR toggles where they differ. Counting set bits is counting lit switches — and n & (n−1) turns off the rightmost lit switch each time.

Interactive diagram

Watch each operator act on the same two numbers bit by bit.

a = 12, b = 10 in binary

Bitwise operators act on each bit position independently. a = 001100, b = 001010.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. The bitwise operators

    AND, OR, XOR, NOT, left/right shift — bit-by-bit semantics.

    20 min
  2. Essential tricks

    Check/set/clear/toggle a bit; n & (n−1); isolate lowest set bit.

    25 min
  3. XOR patterns

    Cancel pairs to find singles; missing number; swap without temp.

    20 min
  4. Counting bits

    Brian Kernighan's method and the DP relation.

    15 min
  5. Bitmasks as sets

    Membership, union/intersection, and subset enumeration.

    25 min
  6. Python-specific gotchas

    Arbitrary-precision ints, negative numbers, masking to 32 bits.

    15 min

Operations

Check, set, clear, and toggle a bit

Build a mask with 1 << k, then AND to test, OR to set, AND-NOT to clear, XOR to toggle.

Check, set, clear, and toggle a bit
def get_bit(x: int, k: int) -> int:    """Value of bit k (0 or 1)."""    return (x >> k) & 1def set_bit(x: int, k: int) -> int:    """Turn bit k on."""    return x | (1 << k)def clear_bit(x: int, k: int) -> int:    """Turn bit k off."""    return x & ~(1 << k)def toggle_bit(x: int, k: int) -> int:    """Flip bit k."""    return x ^ (1 << k)def is_power_of_two(n: int) -> bool:    """A power of two has exactly one set bit."""    return n > 0 and (n & (n - 1)) == 0     # clears the only set bit → 0
Time: O(1)Space: O(1)

Edge cases

  • k must be within the integer's width you care about; Python ints are unbounded, so no overflow.
  • is_power_of_two must guard n > 0 (0 and negatives aren't powers of two).
  • n & (n−1) clears the LOWEST set bit — for a power of two that's the only bit.

Common mistakes

  • Confusing bitwise & with logical and (and short-circuits, & doesn't).
  • Forgetting the n > 0 guard, so 0 wrongly reports as a power of two.

XOR to find the unique element

XOR all numbers: every value appearing twice cancels to 0, leaving only the single unpaired value.

XOR to find the unique element
def single_number(nums: list[int]) -> int:    """Every element appears twice except one. Find it. O(n)/O(1).    Relies on x ^ x = 0 and x ^ 0 = x, and XOR being commutative."""    result = 0    for x in nums:        result ^= x        # pairs cancel; order doesn't matter    return resultdef missing_number(nums: list[int]) -> int:    """nums holds 0..n with one missing. XOR indices against values."""    result = len(nums)                      # start with n    for i, x in enumerate(nums):        result ^= i ^ x                     # each present value cancels its index    return result
Time: O(n)Space: O(1) — beats the O(n)-space hash-set approach

Edge cases

  • Works because XOR is commutative and associative — grouping/order is irrelevant.
  • single_number requires EXACTLY one unpaired element (others in pairs).
  • For elements appearing THREE times except one, XOR doesn't cancel — use bit-counting mod 3.

Common mistakes

  • Reaching for a hash map (O(n) space) when XOR is O(1) space — the intended answer.
  • Applying plain XOR to the 'appears 3 times' variant, where it fails.

Count set bits (Brian Kernighan)

n & (n−1) removes the lowest set bit; loop until zero, counting iterations. Runs once per set bit, not once per bit.

Count set bits (Brian Kernighan)
def count_set_bits(n: int) -> int:    """Number of 1 bits. O(number of set bits), not O(total bits)."""    count = 0    while n:        n &= n - 1          # drop the lowest set bit        count += 1    return countdef count_bits_up_to(n: int) -> list[int]:    """count[i] = set bits in i, for 0..n. DP: O(n)."""    dp = [0] * (n + 1)    for i in range(1, n + 1):        dp[i] = dp[i >> 1] + (i & 1)   # i's bits = (i//2)'s bits + its last bit    return dp
Time: count_set_bits: O(set bits); count_bits_up_to: O(n)Space: O(1) / O(n)

Edge cases

  • n = 0 → 0 set bits (loop never runs).
  • Negative numbers in Python have infinite leading 1s conceptually — mask first if counting a fixed width.
  • The DP relation dp[i] = dp[i>>1] + (i&1) is the elegant 'counting bits' answer.

Common mistakes

  • Looping over all 32/64 bits when Kernighan's runs only per set bit.
  • Counting bits of a negative Python int without masking to the intended width.

Bitmask as a set (subset enumeration)

An integer's bits encode set membership; iterate 0 to 2ⁿ−1 to enumerate every subset in O(2ⁿ).

Bitmask as a set (subset enumeration)
def all_subsets(nums: list[int]) -> list[list[int]]:    """Every subset via bitmasks. O(n · 2^n)."""    n = len(nums)    result: list[list[int]] = []    for mask in range(1 << n):              # 0 .. 2^n - 1        subset = [nums[i] for i in range(n) if mask & (1 << i)]        result.append(subset)               # bit i set ⇒ include nums[i]    return result# Bitmask set operations (all O(1)):#   add element i:        mask |= (1 << i)#   remove element i:     mask &= ~(1 << i)#   test membership i:    mask & (1 << i)#   union / intersection: a | b   /   a & b#   size (popcount):      bin(mask).count("1")
Time: O(n · 2ⁿ) to enumerate all subsetsSpace: O(n) per subset

Edge cases

  • mask = 0 is the empty subset; mask = 2ⁿ−1 is the full set.
  • Only practical for n ≤ ~20 (2²⁰ ≈ 1M masks).
  • Bitmask DP compresses a 'visited set' into one integer — the TSP/assignment technique.

Common mistakes

  • Using bitmask enumeration for large n (2ⁿ explodes past n≈25).
  • Off-by-one between bit position i and element index.

Complexity analysis

OperationBestAverageWorstSpace
Get/set/clear/toggle bitO(1)O(1)O(1)O(1)
XOR single/missing numberO(n)O(n)O(n)O(1)
Count set bits (Kernighan)O(1)O(set bits)O(bits)O(1)
Count bits 0..n (DP)O(n)O(n)O(n)O(n)
Subset enumeration (bitmask)O(2ⁿ)O(n·2ⁿ)O(n·2ⁿ)O(n)

Bit tricks turn many O(n)-space or looping solutions into O(1)-space one-liners — the reason they're worth memorizing.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Bitmask DP: minimum-cost assignment (Hamiltonian-style state)
def min_assignment_cost(cost: list[list[int]]) -> int:    """n workers, n jobs; cost[w][j]. Assign each worker one distinct job    at minimum total cost. Bitmask DP over the set of ASSIGNED jobs.    O(n · 2^n) — feasible for n up to ~20."""    n = len(cost)    FULL = (1 << n) - 1    # dp[mask] = min cost to assign jobs in 'mask' to the first popcount(mask) workers    dp = [float("inf")] * (1 << n)    dp[0] = 0    for mask in range(1 << n):        if dp[mask] == float("inf"):            continue        worker = bin(mask).count("1")       # this many workers already assigned        if worker == n:            continue        for job in range(n):            if not (mask & (1 << job)):      # job still free

What interviewers expect you to know

Tricks to have memorized

  • x ^ x = 0, x ^ 0 = x — XOR cancels pairs (single number, missing number, swap without temp).
  • n & (n−1) clears the lowest set bit — powers of two, Kernighan's bit count.
  • 1 << k builds a single-bit mask; & tests, | sets, & ~ clears, ^ toggles.
  • A bitmask is a set: | union, & intersection, ^ symmetric difference, all O(1).

Python-specific gotchas

  • Python ints are arbitrary precision — no overflow, but negative numbers have conceptually infinite leading 1s. Mask with & 0xFFFFFFFF to simulate 32-bit behavior.
  • bin(x).count('1') is a clean popcount; Python 3.10+ has int.bit_count().
  • & / | are bitwise; and / or are logical (short-circuiting) — a subtle bug source.

When to reach for bits

  • 'Appears twice except one', 'find the missing/duplicate', 'without extra space' → XOR.
  • 'Enumerate all subsets', 'state is a set of ≤ 20 things' → bitmask (possibly bitmask DP).
  • 'Power of two', 'count bits', 'is only one bit set' → the n & (n−1) family.

Common mistakes

Bitwise vs logical operators

& and | operate on bits and don't short-circuit; and/or are boolean. Writing `if x and 1` when you meant `x & 1` is a classic mistake.

Negative numbers in Python

Right-shifting or counting bits of a negative int assumes infinite sign bits. Mask to the intended width (& 0xFFFFFFFF) before bit-counting fixed-size values.

XOR on the wrong variant

Plain XOR finds the single among PAIRS. If elements appear three times (except one), XOR fails — use per-bit counts mod 3.

Missing the power-of-two guard

n & (n−1) == 0 is also true for n = 0. Powers of two require n > 0.

Bitmask on large n

2ⁿ explodes: n = 30 is a billion masks. Bitmask techniques are for n ≲ 20.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (5)

Medium (5)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. What does 12 ^ 10 equal? (12 = 1100, 10 = 1010)
  2. Concept2. How does `n & (n - 1) == 0` (with n > 0) test for a power of two?
  3. Code output3. single_number([4, 1, 2, 1, 2]) using XOR returns…
  4. Scenario4. You must enumerate all subsets of a set of 15 elements. Which technique is clean and feasible?
  5. Concept5. Brian Kernighan's `n &= n - 1` bit-counting loop runs how many times?
0 of 5 answered

Frequently asked questions

Do I really need bit manipulation for interviews?

For the common set — single number, power of two, counting bits, subsets — yes; these appear regularly and have clean bit solutions expected as the optimal answer. Deep bit-twiddling (advanced masks, gray codes) is rarer and role-dependent. Master the identities in the 'tricks to memorize' list and you'll handle most of it.

Why do negative numbers behave strangely with bitwise ops in Python?

Python ints are arbitrary precision and use two's-complement conceptually with infinite sign bits, so ~5 is −6 and right-shifting a negative keeps sign bits. When a problem assumes fixed 32-bit integers, mask with & 0xFFFFFFFF to emulate that width before counting or shifting.

What is bitmask DP and when is it used?

It's DP where a state includes 'which subset of ≤ ~20 items is done', encoded as one integer's bits. It compresses an exponential set-state into an array index, enabling problems like Traveling Salesman and assignment in O(2ⁿ · n) — feasible only for small n but otherwise intractable.

Summary & cheat sheet

Key takeaways

  • Bitwise operators act per bit: & masks, | sets, ^ flips/cancels, << >> scale by powers of two.
  • Memorize: x ^ x = 0, n & (n−1) clears the lowest set bit, 1 << k is a bit mask.
  • XOR solves 'single among pairs' and 'missing number' in O(1) space.
  • A bitmask is a set — O(1) union/intersection/membership; enumerate subsets over 0..2ⁿ−1.
  • In Python, mask to 32 bits when a problem assumes fixed-width integers.

Formulas & cheat sheet

  • test bit k: (x >> k) & 1 · set: x | (1<<k) · clear: x & ~(1<<k) · toggle: x ^ (1<<k)
  • power of two: n > 0 and (n & (n−1)) == 0
  • count bits DP: dp[i] = dp[i>>1] + (i & 1)
  • subset enumeration: for mask in range(1 << n)

Interview checklist

  • I can check/set/clear/toggle a bit from memory.
  • I can solve single-number and missing-number with XOR.
  • I can count set bits with Kernighan's method.
  • I can enumerate subsets with a bitmask and do O(1) set ops.