Bit Manipulation — XOR Tricks, Counting Bits and Powers of Two

Computers store numbers in binary — base 2. 13 is 1101 = 8 + 4 + 0 + 1. Bit manipulation means working directly on these bits. A few tricks solve certain problems in O(1) extra space with almost no code, and interviewers love asking them.

The operators

Operator	Python / Java	Rule	Example (5 = 101, 3 = 011)
AND	a & b	1 if both bits are 1	101 & 011 = 001 (1)
OR	a | b	1 if either is 1	101 | 011 = 111 (7)
XOR	a ^ b	1 if bits are different	101 ^ 011 = 110 (6)
NOT	~a	flip every bit	~5 = -6 (two's complement)
Left shift	a << k	multiply by 2ᵏ	5 << 1 = 10
Right shift	a >> k	divide by 2ᵏ (floor)	5 >> 1 = 2

Everyday bit operations

x >> i & 1          # read bit i (0 or 1)
x | (1 << i)        # set bit i
x & ~(1 << i)       # clear bit i
x ^ (1 << i)        # toggle bit i
x & 1               # 1 if x is odd

Trick 1 — XOR cancels pairs (Single Number)

Every number appears twice except one. Find it in O(n) time and O(1) space.

XOR has three magic properties: a ^ a = 0, a ^ 0 = a, and order doesn't matter. XOR everything together — pairs cancel, the single number remains.

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

int singleNumber(int[] nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}

[4, 1, 2, 1, 2] → 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4.

Missing Number (0…n with one missing) uses the same trick: XOR all indices 0…n with all values — everything cancels except the missing number. (The sum formula n(n+1)/2 − sum(nums) also works.)

Trick 2 — n & (n − 1) removes the lowest set bit

Subtracting 1 flips the lowest 1 bit and every 0 after it. ANDing with the original clears that lowest 1:

n       = 1011000
n − 1   = 1010111
n & n−1 = 1010000   ← lowest 1 removed

Count the 1 bits (Hamming weight): keep removing the lowest bit until zero — the loop runs once per set bit.

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

Power of two: a power of two has exactly one set bit, so removing it gives zero.

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

Trick 3 — Build answers from smaller numbers (Counting Bits)

Return the number of 1 bits for every number 0…n. i >> 1 is i without its last bit, which we've already computed:

def count_bits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

O(n) — a tiny dynamic programming solution.

Trick 4 — Reverse bits

Take bits from the right of n one at a time and push them onto the left of the result:

def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Bitmasks for subsets

An integer from 0 to 2ⁿ − 1 can represent every subset of n items: bit i set means "item i included". This is a compact alternative to backtracking when n is small (≤ 20).

def subsets(nums):
    n = len(nums)
    return [[nums[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]

Language notes

• Java ints are 32-bit signed; use >>> for an unsigned right shift (fills with 0 instead of the sign bit) — needed in Number of 1 Bits for negative inputs.
• Python ints are unlimited in size; mask with & 0xFFFFFFFF when a question assumes 32-bit numbers.

How to recognise bit manipulation

• "Every element appears twice except one" → XOR.
• "Count set bits", "power of two", "reverse bits".
• O(1) extra space required with duplicates/missing numbers.
• Subsets of a small set → bitmask.

Common mistakes

1. Operator precedence: in Java and C++, == binds tighter than &, so x & 1 == 0 means x & (1 == 0) — a compile error in Java. Write (x & 1) == 0. (Python happens to parse it the way you expect, but the parentheses make it clear in every language.)
2. Signed shifts in Java on negative numbers — use >>>.
3. Forgetting n > 0 in the power-of-two check (0 is not a power of two).

Key takeaways

• XOR cancels pairs: a ^ a = 0, a ^ 0 = a.
• n & (n − 1) drops the lowest set bit → counting bits, power of two.
• Bitmasks represent subsets compactly.