Bit Manipulation

XOR cancels duplicates, & isolates the lowest set bit, and shifts replace expensive loops — pocket-sized algorithms that ace one-shot interview problems.

intermediatePractice Full theoryPrereq:Complexity & Big-O

Start practice Read the theory See all problems

What you'll learn

Use AND, OR, XOR, NOT, and shifts fluently and know their truth tables
Get, set, clear, and toggle the i-th bit with mask idioms
Apply XOR cancellation to single-number and missing-number problems
Count set bits with Brian Kernighan's n & (n-1) trick
Enumerate subsets with bitmasks
Avoid the signed-shift and overflow traps in Java

When to reach for this

Signals (use it)

"Every element appears twice except one" → XOR everything
"Count the 1 bits" / Hamming weight / Hamming distance
"Find the missing number" in 0..n → XOR or sum
Enumerate all subsets of a small set (n ≤ ~20) → bitmask
Check power of two, swap without temp, multiply/divide by 2^k

Anti-signals (don't)

Large n where you'd brute-force 2^n masks → needs DP/pruning
Problem is about values, not their bit patterns → normal arithmetic
Readability matters more than the micro-trick → prefer clear code

Theory & deep dive

Bit manipulation works directly on the binary representation of integers using the bitwise operators AND, OR, XOR, NOT, and shifts. A handful of identities replace whole loops: XOR cancels equal values (a^a = 0), letting you find a lone unpaired number in O(1) space; AND with (x-1) clears the lowest set bit, powering fast popcount; and shifts multiply or divide by powers of two for free.

These tricks are 'pocket-sized' — each is a few lines — but they're high-leverage in interviews because they turn O(n) space or O(n log n) time into O(1)/O(log n). The skill is recognising the signal ('every element appears twice except one', 'count the set bits', 'enumerate all subsets') and recalling the matching identity.

This module covers the operator toolkit, the get/set/clear/toggle idioms, the XOR family, popcount, and bitmask subset enumeration — with the negative-number and overflow gotchas that trip people up.

The big idea in plain words

Picture a number as a row of light switches, each one either on (1) or off (0). Bit tricks let you flip, read, and combine those switches directly, which is about as fast as a computer can go. The star of the show is XOR, a 'toggle': pairing any switch with itself turns it off, because a XOR a = 0.

Example: find the number that appears only once in [4, 1, 2, 1, 2] while every other number appears twice. XOR them all together; the matching pairs cancel each other out (1 XOR 1 = 0, and 2 XOR 2 = 0), leaving just 4 - the lonely value - and you used no extra memory at all.

The operator toolkit

Operator	Symbol	Effect	Identity
AND	`&`	1 only if both bits 1	`x & 0 = 0`, `x & x = x`
OR	`\|`	1 if either bit 1	`x \| 0 = x`
XOR	`^`	1 if bits differ	`x ^ x = 0`, `x ^ 0 = x`
NOT	`~`	flips every bit	`~x = -x - 1`
Left shift	`<<`	×2 per shift	`x << k = x · 2^k`
Right shift	`>>`	÷2 per shift	`x >> k = x / 2^k`

The two workhorses are XOR (self-cancelling, commutative) and AND (masking and isolating bits). Commit x ^ x = 0 and x & (x-1) (clears lowest set bit) to memory — they power most of the tricks.

Watch out

In Java use >>> (unsigned right shift) for bit counting, not >> (signed/arithmetic shift), which copies the sign bit and loops forever on negative numbers. Python integers are arbitrary-precision with no sign-bit width, so behave differently — mask with & 0xFFFFFFFF when emulating 32-bit.

Get / set / clear / toggle a bit

These four idioms manipulate the i-th bit (0-indexed from the right). They're the vocabulary every other trick is written in.

Goal	Expression
Get bit i	`(x >> i) & 1`
Set bit i (to 1)	`x \| (1 << i)`
Clear bit i (to 0)	`x & ~(1 << i)`
Toggle bit i	`x ^ (1 << i)`
Lowest set bit	`x & (-x)`
Clear lowest set bit	`x & (x - 1)`
Is power of two	`x > 0 && (x & (x-1)) == 0`

1 << i builds a mask with only bit i set; combining it with AND/OR/XOR reads or edits that one bit.

Match the signal to the trick:

The XOR family

XOR's self-cancellation is the most useful single fact in this module. If every element appears twice except one, XOR-ing them all leaves just the unpaired value — the pairs cancel to 0. The same idea finds a missing number in 0..n: XOR all indices and all values; everything cancels except the missing one.

Java· Missing number in 0..n

int missingNumber(int[] nums) {
    int xor = nums.length;           // start with n
    for (int i = 0; i < nums.length; i++)
        xor ^= i ^ nums[i];          // index ^ value, all cancel
    return xor;                       // the missing one remains
}

Counting set bits (Brian Kernighan)

To count the 1-bits (population count / Hamming weight), the naive way checks all 32 bits in O(bits). Brian Kernighan's trick is faster when bits are sparse: n & (n-1) clears the lowest set bit, so you loop only as many times as there are set bits. Hamming distance between two numbers is just the popcount of their XOR.

Python· Count set bits (Kernighan)

def count_bits(n):
    count = 0
    while n:
        n &= n - 1     # drop the lowest set bit
        count += 1
    return count

# Hamming distance: bin(a ^ b).count('1')

Bitmask subset enumeration

A set of n elements has 2^n subsets, and each subset maps to an n-bit integer where bit i means 'element i is included'. Looping a mask from 0 to 2^n − 1 enumerates every subset — a clean, allocation-free alternative to recursive backtracking when n is small (≤ ~20). This bitmask-as-state idea also underpins bitmask DP (e.g. travelling salesman, assignment problems).

Python· All subsets via bitmask

def subsets(nums):
    n = len(nums)
    res = []
    for mask in range(1 << n):          # 0 .. 2^n - 1
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        res.append(subset)
    return res

Tip

Iterate submasks of a mask with sub = (sub - 1) & mask — a classic for bitmask DP that visits every subset of the set bits in O(3^n) total across all masks.

How to talk about this in the interview

“Recognise the signal and name the identity: "Every number appears twice except one — XOR cancels the pairs, so XOR-ing everything leaves the answer in O(1) space." or "To count set bits, n & (n-1) clears the lowest set bit, so I loop once per set bit." Show you know the gotchas: "I'll use unsigned right shift in Java to avoid the sign-bit issue." These tricks read as senior because they replace O(n) space or extra loops with a one-liner — state that improvement explicitly.”

Common mistakes

–Using signed `>>` instead of `>>>` in Java for bit counting on negative numbers (infinite loop)
–Operator precedence: `&`, `|`, `^` bind looser than `==` — parenthesise `(x & mask) == 0`
–Forgetting `1 << i` overflows int at i ≥ 31 in Java — use `1L << i` for 64-bit masks
–Confusing logical (&&/||) with bitwise (&/|) operators
–Assuming Python ints are 32-bit — they're arbitrary precision; mask explicitly when emulating fixed width
–Enumerating 2^n masks when n is large (>~20) — exponential blowup

Complexity summary

Bit operations are O(1) on machine-word integers. XOR-scan single-number is O(n) time, O(1) space. Kernighan popcount is O(set bits) per number. Bitmask subset enumeration is O(2^n · n); submask iteration over all masks is O(3^n).

Practice problems

20 total