Bit Manipulation Isn't Magic. It's Five Patterns.

You're staring at a problem. The constraint says 0 <= n <= 2^31 - 1. The examples involve powers of two. The problem asks for O(1) space. You've seen solutions online that use n & (n - 1) and collect 10 upvotes and zero explanation.

Bit manipulation problems feel like they require a secret handshake. They don't. Five tricks, a handful of recognition signals. Map the signals to the tricks and they stop feeling like summoning a demon and start feeling like looking something up.

Five Ways the Problem Is Begging You to Use Bits

Signal 1: The constraint includes powers of 2. "0 <= n <= 2^31 - 1" or "1 <= k <= 16" is the problem telling you something. Powers of two align with register widths and bitmask sizes. When you see this, ask what the binary representation is doing. Not because you're clever. Because the problem literally told you to.

Signal 2: "O(1) space" with no data structures allowed. If you cannot use a hash set or array and the problem involves finding a missing or unique element, XOR almost certainly gets you there. This constraint collapses the solution space to bitwise arithmetic.

Signal 3: The problem asks you to count, detect, or manipulate individual bits. "How many 1-bits does n have?" or "Is n a power of two?" are bit problems by definition. So are subtler variants: "find the longest run of consecutive 1s after at most one flip."

Signal 4: The input represents a set and n is at most 20. Each possible subset maps to an integer whose bits mark which elements are included. This is bitmask DP. The n <= 20 ceiling is the tell.

Signal 5: The problem uses the words "XOR", "toggle", or "flip." Problem authors who use this language are pointing at the technique directly. They are not being subtle. Take the hint.

Forget the Operators. Memorize the Idioms.

You already know AND, OR, XOR, and NOT. What you need is the cheat sheet:

n & 1           → Is n odd?
n & (1 << k)    → Is bit k set?
n | (1 << k)    → Set bit k
n & ~(1 << k)   → Clear bit k
n ^ (1 << k)    → Toggle bit k
n & (n - 1)     → Clear the rightmost set bit
n & -n          → Isolate the rightmost set bit

The last two are where almost all the interview action lives. Everything else is setup.

XOR Cancels Pairs. That's the Whole Trick.

The textbook definition of XOR is "outputs 1 when bits differ." Accurate. About as useful as reciting the dictionary definition of "loop" while your code is on fire.

The useful model: XOR cancels any value that appears an even number of times.

Two properties make this work:

x ^ x = 0 (self-cancellation)
x ^ y = y ^ x (commutativity)

Because XOR is commutative and associative, you can reorder any chain freely. Every pair of equal values cancels to zero. Whatever survives appeared an odd number of times.

LeetCode 136 (Single Number): XOR every element. Pairs cancel. The unique value remains.

def single_number(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result ^= n
    return result

O(n) time, O(1) space, no hash map needed.

LeetCode 260 (Single Number III) has two unique elements. XOR everything and you get a ^ b. That value has at least one set bit, because a != b. That bit is a position where a and b disagree. Partition the array by whether that bit is 0 or 1: every duplicated element lands in the same group as its pair, the two uniques land in different groups. XOR each group.

def single_number_iii(nums: list[int]) -> list[int]:
    xor_all = 0
    for n in nums:
        xor_all ^= n

    diff_bit = xor_all & (-xor_all)

    a, b = 0, 0
    for n in nums:
        if n & diff_bit:
            a ^= n
        else:
            b ^= n
    return [a, b]

xor_all & (-xor_all) isolates the rightmost set bit via two's complement. In two's complement, -x flips all bits then adds 1. That carry ripples through every trailing zero until it hits the rightmost 1. So -x and x agree on exactly that bit and disagree everywhere else. Not a trick. Just arithmetic.

Interviewer thinking candidate is a genius, but they just know Hello World Interviewer energy when you solve Single Number in 5 lines of XOR and explain every step.

One Formula, Two Interview Problems

When you subtract 1 from any number, the rightmost 1 flips to 0 and every 0 below it flips to 1. n & (n - 1) zeroes those newly-flipped bits. Result: n with its rightmost set bit cleared.

Power of two check (LeetCode 231). A power of two has exactly one set bit. Clearing it gives zero:

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

The n > 0 guard is not optional. 0 & (-1) is 0, so without it, zero incorrectly registers as a power of two. Every solution that skips this guard is wrong for the edge case.

Hamming weight / Brian Kernighan's algorithm (LeetCode 191). Loop until n reaches zero, counting iterations. Each iteration clears exactly one set bit:

def hamming_weight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

Most candidates write a 32-iteration scan. This runs in O(k) time where k is the number of set bits. Three 1-bits means three iterations, not 32. It is a small win on most inputs and a big win when the interviewer asks "can you do better?"

The Python Trap Nobody Warned You About

Most bit manipulation tutorials are written in Java or C++. Two traps hit Python users specifically.

Trap 1: ~n is not "flip all bits."

Python integers have arbitrary precision. There is no fixed-width bit flip. Python defines ~n = -(n + 1):

>>> ~5
-6    # Not 0b11111010. Not 26. Just -(5 + 1).

When you need a fixed-width bit flip, apply a mask explicitly:

flip_within_32_bits = ~n & 0xFFFFFFFF

Trap 2: Python has no unsigned right shift.

Java's >>> fills vacated bits with zeros regardless of sign. Python's >> is arithmetic: it fills vacated bits with copies of the sign bit. For problems that simulate a 32-bit system:

# Simulate Java's n >>> 1 in Python
(n & 0xFFFFFFFF) >> 1

The mask converts Python's arbitrary-precision signed representation into the 32-bit window the problem expects. Forget the mask and your solution sails through every positive test case, then silently produces wrong answers on negative inputs in a way that takes 20 minutes to debug.

Failed technical interview meme The ~n trap catches someone in every LeetCode contest. Today it will not be you.

When the Problem Is Really About Subsets

Bitmask DP is a different beast from the tricks above. You are using an integer as a compact representation of a subset, not manipulating a single value's bits.

The tell is n <= 20 and the problem asks you to visit, assign, or partition every element. Classic examples: Traveling Salesman, assignment problems, matching with constraints.

Given n elements, represent every subset as an integer from 0 to 2^n - 1. Bit k is 1 if element k is included. Run DP over all 2^n states.

n = len(elements)
INF = float('inf')
dp = [INF] * (1 << n)
dp[0] = 0

for mask in range(1, 1 << n):
    for i in range(n):
        if not (mask >> i & 1):
            continue
        prev_mask = mask ^ (1 << i)
        dp[mask] = min(dp[mask], dp[prev_mask] + cost(i, prev_mask))

Enumerating all subsets of a given mask:

sub = mask
while sub > 0:
    process(sub)
    sub = (sub - 1) & mask

(sub - 1) & mask clears the lowest set bit of sub and masks off any bits not in mask. Across all masks from 0 to 2^n - 1, this loop runs 3^n total iterations. That sounds bad. For n = 20 it is about 3.5 billion. The problem constraints are the guard here, not you.

For a deeper look at when DP applies, see when to use dynamic programming.

Read the Signal, Pick the Trick

When a problem looks like it might want bits, work through four questions:

Write out the binary of one or two concrete examples. Look for what changes and what stays fixed across inputs and outputs.
Does XOR solve this? Duplicate cancellation, unique elements, toggling state. Try XOR first. If it does not quite work, check whether a partition by a differing bit finishes the job.
Does n & (n-1) apply? Count set bits, detect powers of two, or clear one bit at a time. Use n & -n to isolate the rightmost bit.
Is n <= 20 with a set of elements? Bitmask DP. State is a bitmask, transitions set or clear one bit.

If you reach none of these and still suspect bits, write out the cheat sheet and check what each operator does to your concrete example. The pattern is usually visible once you see the binary.

If you want to practice recognizing these patterns in real time, under pressure, with a voice-based interviewer probing your reasoning, SpaceComplexity runs full mock interviews across the bit manipulation set and gives rubric-based feedback on communication and approach, not just whether your code is correct.

Recap

Five signals: powers-of-2 constraints, O(1) space with uniqueness, individual bit ops, n <= 20 set membership, and "XOR/toggle/flip" language in the problem statement.
XOR cancels pairs via commutativity and self-cancellation. Single Number III extends this with a partition step using xor_all & (-xor_all) to isolate the rightmost differing bit.
n & (n-1) clears the rightmost set bit. Power of two if result is zero. Brian Kernighan's algorithm counts set bits in O(k) iterations, not O(32).
Python's ~n equals -(n+1). Mask with & 0xFFFFFFFF for fixed-width behavior. No unsigned right shift either.
Bitmask DP: n <= 20, choosing from a set. Enumerate submasks with sub = (sub - 1) & mask. Total iterations across all masks is 3^n.