Bit Manipulation Explained: XOR Tricks, Masks & Set Bits

A room with 8 light switches. Any on/off combination is one "state" — 2⁸ = 256 states, all describable by a single byte. Flip switch 3: one flick. Check whether switch 5 is on: one glance. No loops, no lists — the switches ARE the data structure.

Every integer in your computer is exactly this: a row of switches. 13 is 1101 — switches 0, 2 and 3 on. Bit manipulation is operating on the switches directly, and it buys two things: some O(n)-space problems collapse to O(1) one-liners, and a whole family of interview tricks — XOR magic, power-of-two tests, bitmask states — turns from occult to obvious.

The six operators, anchored

a, b = 12, 10          # 1100, 1010

print(bin(a & b))       # AND:  1 where BOTH are 1     -> 1000 (8)
print(bin(a | b))       # OR:   1 where EITHER is 1    -> 1110 (14)
print(bin(a ^ b))       # XOR:  1 where they DIFFER    -> 0110 (6)
print(bin(a << 1))      # left shift:  x2              -> 11000 (24)
print(bin(a >> 2))      # right shift: //4             -> 11 (3)
print(~a)               # NOT: flips all bits          -> -13 (see below)

0b1000
0b1110
0b110
0b11000
0b11
-13

Anchor each with one word: AND filters (keeps bits both agree on), OR accumulates (turns bits on), XOR differences (1 exactly where they disagree). Shifts move place values — each place is a power of 2, so << 1 doubles, >> 1 halves. And that odd ~a = −13? Two's complement plus Python's unbounded integers: NOT is best used with a width mask in interviews, not bare.

Masks: check, set, clear, toggle

How do you touch exactly ONE bit without disturbing the rest? Build a number with only that bit on — 1 << k — called a mask, and combine it with the right operator:

def check(n, k):   return (n >> k) & 1      # is bit k on?
def set_(n, k):    return n | (1 << k)      # turn it on
def clear(n, k):   return n & ~(1 << k)     # turn it off
def toggle(n, k):  return n ^ (1 << k)      # flip it

n = 0b1010
print(check(n, 1), check(n, 2))
print(bin(set_(n, 2)), bin(clear(n, 3)), bin(toggle(n, 0)))

1 0
0b1110 0b10 0b1011

AND tests, OR sets, AND-NOT clears, XOR toggles — and each leaves every other bit untouched, which is what makes packed flags safe: file permissions (rwx = 3 bits), feature toggles, chess-engine boards. Learn the four as one unit; every bit problem decomposes into them.

XOR: the self-erasing operator

XOR earns its own section because two tiny properties make it an interview machine: x ^ x = 0 (anything cancels itself) and x ^ 0 = x (zero is invisible) — plus order never matters. Consequence: XOR a whole list together, and everything appearing an even number of times evaporates.

Problem: every number in [4, 1, 2, 1, 2] appears twice except one — find it. The dict-count solution costs O(n) space; the follow-up "without extra memory?" is asking for XOR by name:

def single(arr):
    acc = 0
    for x in arr:
        acc ^= x           # pairs cancel, wherever they sit
    return acc

print(single([4, 1, 2, 1, 2]))

Dry run: the single number

acc = 000 (0)
^4  -> 100 (4)
^1  -> 101 (5)
^2  -> 111 (7)
^1  -> 110 (6)    <- the 1s just cancelled
^2  -> 100 (4)    <- the 2s just cancelled

answer: 4. Order never mattered - XOR is commutative,
so every pair annihilates no matter where it sits.

Same self-cancellation solves missing number from 1..n: XOR the full range with the actual array — every present value meets its twin and vanishes; the absentee survives. (The sum formula n(n+1)/2 − actual also works; XOR's edge is immunity to fixed-width overflow — one sentence worth saying.)

n & (n−1): the lowest-bit eraser

Why does subtracting 1 target exactly the lowest set bit? Borrowing: the −1 flips trailing 0s to 1s until it hits the lowest 1, flips that to 0, and stops — everything above is untouched. AND the two numbers and the whole disagreement zone dies: n & (n−1) clears exactly the lowest set bit. Two famous consequences:

def count_bits(n):            # Kernighan: ONE loop per SET bit
    count = 0
    while n:
        n &= n - 1            # erase the lowest 1
        count += 1
    return count

def is_power_of_two(n):       # one set bit -> one erase -> zero
    return n > 0 and (n & (n - 1)) == 0

print(count_bits(29), is_power_of_two(64), is_power_of_two(24))

4 True False

The power-of-two one-liner is among the most-asked bit questions anywhere — and the n > 0 guard is the trap inside it: without it, 0 passes the AND test and sneaks through. Sibling worth knowing: n & -n isolates the lowest set bit instead of clearing it.

Shifts are arithmetic you already use

Quick check: what is 5 << 3? If you started drawing bits, take the shortcut: shifting left by k multiplies by 2ᵏ — 5 × 8 = 40. And you have been using bit-halving all course: binary search's midpoint, the heap's parent index (i−1)//2, every halving loop — all >> 1 in disguise.

The fluency that matters: reading x * 2, x // 2, x % 2 and x << 1, x >> 1, x & 1 as the same operations in two notations. (Don't "optimise" Python by swapping arithmetic for shifts — interpreters handle that; the win is reading code, not micro-tuning it.)

Bitmasks as sets: the endgame

The advanced payoff: an integer can represent a set over up to ~60 items — bit i on means item i is in. Set operations become single instructions: union = OR, intersection = AND, membership = the check mask. And "every subset" = counting from 0 to 2ⁿ−1:

items = ["idli", "dosa", "vada"]

for mask in range(1 << len(items)):        # 0..7 - every subset
    subset = [items[i] for i in range(len(items)) if mask & (1 << i)]
    print(f"{mask:03b}", subset)

000 []
001 ['idli']
010 ['dosa']
011 ['idli', 'dosa']
100 ['vada']
101 ['idli', 'vada']
110 ['dosa', 'vada']
111 ['idli', 'dosa', 'vada']

Compare with the backtracking subsets — same 2ⁿ output, no recursion, and the mask doubles as a hashable dict key. That last property powers bitmask DP (state = the set of already-used items — the travelling-salesman pattern): deriving it is beyond placement scope, but recognising "n ≤ 20, subsets as states" as its signature earns real credit.

What if...?

What if TWO numbers appear once and the rest twice? XOR everything → you get a XOR b (pairs cancelled). It's non-zero, so some bit differs between a and b — partition all numbers by that bit and XOR each side: each partition holds exactly one of the two singles. The standard level-2 follow-up, solved by running the level-1 trick twice.

What if elements repeat THREE times except one? XOR pairs-cancellation needs even multiplicities — it breaks. Count each bit position mod 3 instead. Knowing the boundary of a trick matters as much as the trick.

What if n is 0 or negative in these tricks? 0 has no set bits (Kernighan returns 0 — fine; power-of-two must guard). Negatives in Python carry infinite sign bits conceptually — mask to a width (n & 0xFFFFFFFF) when a problem assumes 32-bit behaviour.

What if I write x & 1 == 0? Precedence trap: it parses as x & (1 == 0). Bracket every bitwise expression: (x & 1) == 0. This single parenthesis bug fails more written-round submissions than any bit concept does.

Common mistakes

• Confusing & with and — 12 and 10 is 10; 12 & 10 is 8.
• The missing n > 0 guard in power-of-two.
• Unbracketed bitwise expressions (precedence).
• Expecting ~x to give a clean flipped pattern in Python — it's −(x+1); mask to a width when needed.
• Using the XOR single-number trick on thrice-repeating inputs.
• Off-by-one on bit positions: bit 0 is the ONES place — the rightmost.

How do I recognise bit problems?

• "without extra memory" on pair/missing/duplicate questions → XOR cancellation.
• "power of two", "count set bits", "binary representation" → masks and n&(n−1).
• Flags, permissions, on/off states → the check/set/clear/toggle quartet.
• n ≤ 20 with "visit/assign all" flavour → subsets as bitmask states (name bitmask DP).
• MCQs printing a & b, a | b, a ^ b on small numbers → convert to binary and compute; practise until it's 30 seconds.

Quick revision

All O(1) per operation, O(1) space — the entire appeal. The real "worst case" is readability: comment any bit trick a colleague couldn't read aloud.

One thing to remember

Numbers are rows of switches: masks touch one switch cleanly, and XOR makes anything paired vanish. Those two facts are 90% of every bit question ever asked.

Practice Zone — PYQs from real selection rounds

Six MCQs, then two drills: the XOR single-number with the accumulator shown, and counting set bits both ways with iteration counts compared.

Q1Bitseasy

13 in binary is 1101. What is 13 & 1 (bitwise AND with 1), and what does it tell you?

Asked in

a1 — the last bit is 1, so 13 is oddb0 — 13 is evenc13 — AND with 1 changes nothingd14

Q2Bitseasy

Left-shifting a number by 1 (n << 1) is equivalent to:

Asked in

aDividing by 2bMultiplying by 2 — every bit moves to the next higher place valuecAdding 1dReversing the bits

Q3XORmedium

XOR's two key properties for interview tricks are:

Asked in

ax ^ x = 0 and x ^ 0 = x — so XOR-ing a full list cancels pairs and leaves the unpaired valuebx ^ x = x and x ^ 0 = 0cXOR is the same as ORdXOR only works on positive numbers

Q4Bitsmedium

What does n & (n − 1) do, and what follows from it?

Asked in

aClears the LOWEST SET BIT of n — so it counts set bits fast, and n & (n−1) == 0 tests for powers of twobSets the lowest zero bitcHalves ndNegates n

Q5Bitsmedium

To CHECK bit k of n, SET it, and CLEAR it, the mask expressions are:

Asked in

acheck: n & (1 << k); set: n | (1 << k); clear: n & ~(1 << k)bcheck: n | (1 << k); set: n & (1 << k); clear: n ^ (1 << k)ccheck: n ^ k; set: n + k; clear: n − kdAll three use XOR

Q6XORhard

Numbers 1..n with one missing: [1, 2, 4, 5] (n = 5). The O(1)-space XOR method computes:

Asked in

a(1^2^3^4^5) ^ (1^2^4^5) = 3 — every present number cancels, leaving the missing onebThe sum 15 − 12 = 3 (which also works, but can overflow fixed-width sums)cBoth (a) and (b) are valid; XOR avoids the overflow concern of the sum methoddNeither works without sorting

Hands-on tasks:

FAQ

Switches flipped. One lesson left — turning eleven techniques into one skill: reading a fresh problem and knowing what it wants — Lesson 12: Problem Patterns & Interview Strategy →