Think in binary. XOR, AND, shifts - a small toolkit that solves a surprising range of problems.

Bit Manipulation

What is bit manipulation?

Every integer is stored in binary - a sequence of 0s and 1s. Bit manipulation operates on those individual bits using hardware-level operators (AND, OR, XOR, shift) instead of arithmetic. These operations are O(1) per call and often collapse problems that look O(n) into a single pass with O(1) extra space.

Python integers are arbitrary precision, so there is no 32-bit overflow to worry about. The main quirk is ~n = -(n+1) rather than a simple bit flip, because Python extends the sign bit infinitely. In Java and C++ interviews you must account for 32-bit sign bits and integer overflow, so it is worth noting the difference when asked in a cross-language context.

Bit manipulation is not a general-purpose technique. It appears in a specific cluster of problems: finding the unique element among duplicates (XOR cancellation), checking or setting flags (AND/OR with masks), counting set bits (popcount), and generating all subsets via bitmask enumeration.

The most important operator to internalize is XOR (^): a ^ a = 0 (self-inverse - any number cancels itself), a ^ 0 = a (identity - zero changes nothing), and XOR is commutative and associative (order never matters). These three properties together mean XORing a list of numbers cancels every even-count duplicate and leaves only the unique element.

Core operations

Operation	Symbol	Example	Notes
AND	`&`	`5 & 3 = 1` (101 & 011 = 001)	Both bits must be 1; used for masking
OR	`\|`	`5 \| 3 = 7` (101 \| 011 = 111)	Either bit is 1; used for setting bits
XOR	`^`	`5 ^ 3 = 6` (101 ^ 011 = 110)	Bits differ; used for toggling and cancellation
NOT	`~`	`~5 = -6`	Flips all bits; in Python `~n = -(n+1)`
Left shift	`<<`	`1 << 3 = 8`	Multiply by 2^k
Right shift	`>>`	`16 >> 2 = 4`	Divide by 2^k (floor)

Key patterns

XOR cancellation

XOR every element together. Duplicate pairs cancel to 0; the single unique element remains. This works because XOR is commutative, associative, self-inverse (n ^ n = 0), and has 0 as its identity (n ^ 0 = n), so order of XOR never matters.

Example: the single number. Folding [4, 1, 2, 1, 2] through XOR: the running result goes 4, 5, 7 as the values land, then the second 1 flips it back to 6 and the second 2 flips it to 4 - each duplicate pair cancels itself to 0. The lone 4 is never cancelled, so the final result is 4. The visualizer below shows the binary of result after every step.

VisualizationSingle Number

0/6

result

result (binary)

nums

Start with result = 0. Every number will be XORed into it.

def single_number(nums):▶    result = 0    for num in nums:        result ^= num    return result

Note

XOR cancellation only works when duplicates appear an even number of times - if each duplicate appears 3 times instead of 2, n ^ n ^ n = n, not 0. Confirm the problem guarantees even-count duplicates before applying this trick.

Power-of-two check

A power of two has exactly one bit set: 1, 10, 100, 1000. Subtracting 1 flips that bit and sets all lower bits: 8 - 1 = 7 means 1000 - 1 = 0111. ANDing n & (n-1) clears the lowest set bit; if the result is 0, exactly one bit was set.

Example: is it a power of two?. Test 16 (10000): 16 - 1 = 15 is 01111, the two share no set bits, and 16 & 15 = 0, so yes. Test 18 (10010): subtracting 1 flips only the lowest set bit, giving 17 (10001), and 18 & 17 = 16, a non-zero leftover that exposes the second set bit - so no. The visualizer below lines up the three bit rows for either n.

VisualizationPower of Two

0/2

verdict

power of two

n = 8

n - 1 = 7

n & (n - 1)

n = 8. A power of two has exactly one set bit. Compute n & (n - 1).

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

Note

Always guard n > 0 - 0 & (0 - 1) evaluates to 0 in Python due to arbitrary-precision arithmetic, which would incorrectly classify 0 as a power of two without the guard.

Bit masking

Use a mask 1 << k to target bit position k (0-indexed from the right). Four independent operations - get, set, clear, toggle - each takes one line and one mask.

Example: read and flip one bit. Take n = 20 (10100) and k = 2: the get reads bit 2 as 1, set ORs in 1 << 2 = 4 but bit 2 is already 1 so n stays 20, and clear ANDs against ~4, dropping exactly that bit to give 16 (10000). Toggle XORs the same mask and flips the bit off, also landing on 16. The visualizer below highlights bit k of num as each mask lands.

VisualizationRead/write the k-th bit

0/4

num

mask = 1 << 2

num = 20

Target bit k = 2 (the highlighted cell). The mask 1 << 2 marks that position.

def get_bit(num, k):▶    return (num >> k) & 1      # read bit k def set_bit(num, k):    return num | (1 << k)      # force bit k to 1 def clear_bit(num, k):    return num & ~(1 << k)     # force bit k to 0 def toggle_bit(num, k):    return num ^ (1 << k)      # flip bit k

Note

n & (n-1) clears the lowest set bit; n & (-n) isolates it - these two companion tricks appear constantly. n & (n-1) removes the lowest 1-bit (used in popcount loops). n & (-n) returns a number with only the lowest 1-bit of n set (used in Fenwick trees and to iterate over set bits one by one).

Bitmask enumeration

For a set of n elements, every subset corresponds to an n-bit integer from 0 to 2^n - 1. Bit k is set if and only if element k is in the subset. Iterate all 2^n subsets by looping masks from 0 to (1 << n) - 1.

Example: all subsets of [a, b, c]. Masks 0 through 7 cover all 2^3 combinations: mask 5 is binary 101, and bit 0 picks a while bit 2 picks c, yielding {a, c}; mask 0 picks nothing (the empty set) and mask 7 picks everything. The loop reads each mask's bits low to high and builds the subset in one pass. The visualizer below walks mask 0 to 7, showing which bits select which elements.

VisualizationEvery subset as a mask

0/8

mask

subset

{ } (empty)

subsets

subset

mask = 0 (binary)

mask = 0: set bits pick { } (empty). Stepping mask 0..7 enumerates all 2^3 subsets.

def all_subsets(elements):    n = len(elements)    result = []▶    for mask in range(1 << n):▶        subset = [elements[k] for k in range(n) if mask & (1 << k)]▶        result.append(subset)    return result

When to reach for bit manipulation

The problem says "all elements appear twice except one" or "find the element that appears once" - XOR cancellation.
You need to check if a number is a power of two or count how many times a number is divisible by 2.
The problem involves subset enumeration where n is small (n <= 20) - iterate bitmasks from 0 to 2^n - 1.
You need to pack multiple boolean flags into a single integer - permissions, visited states in bitmask DP.
The problem involves swapping two values without a temp variable - a ^= b; b ^= a; a ^= b.
The problem mentions XOR explicitly in the statement, or asks about Hamming distance between two numbers.
A DP state tracks which elements have been visited and n is small - encode the state as a bitmask integer.