Bit Manipulation Essentials for Coding Interviews

Why bit manipulation shows up in interviews

Bit manipulation is one of those topics that looks intimidating at first, then becomes very practical once you see the pattern. Interviewers like it because it tests more than syntax: you need to understand how integers are represented, how to reason about operations at the bit level, and when a bit trick can replace a slower loop or extra memory.

The good news is that most interview questions in this area repeat the same few ideas:

• XOR cancels matching values
• Shifting isolates individual bits
• Bit masks let you test or modify one position at a time
• Counting bits often turns into a small repeated pattern

If you can recognize those ideas, a lot of problems become straightforward.

Problem statement: what you need to be able to do

In interviews, bit manipulation questions usually fall into a few buckets:

1. Find the single number when every other value appears twice.
2. Find the unique number when values appear three times or in a mixed pattern.
3. Count set bits in every number from 0 to n.
4. Check, set, clear, or toggle bits in an integer.
5. Use bit masks to track states efficiently.

This post focuses on the essentials you see most often: XOR, single number, and counting bits.

Core intuition: think in binary, not decimal

A normal integer is really a collection of bits. Bit manipulation works because operations on those bits are predictable:

• & compares bits and keeps 1 only where both are 1
• | keeps 1 where either bit is 1
• ^ (XOR) keeps 1 where bits differ
• ~ flips bits
• << shifts bits left
• >> shifts bits right

The most important one for interviews is XOR.

XOR rules you should memorize

XOR has a few properties that make it ideal for interview problems:

• a ^ a = 0
• a ^ 0 = a
• XOR is commutative: a ^ b = b ^ a
• XOR is associative: (a ^ b) ^ c = a ^ (b ^ c)

That means if you XOR a list of numbers, every pair of equal values cancels out, and only the unmatched value remains.

Worked example 1: Single Number

Problem

Given an array where every number appears twice except one, find the number that appears once.

Example:

nums = [4, 1, 2, 1, 2]

Answer: 4

Why XOR works

If you XOR all numbers together:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

All duplicates vanish.

Python solution

from typing import List

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

Step-by-step trace

For nums = [4, 1, 2, 1, 2]:

• Start: result = 0
• result ^= 4 → 4
• result ^= 1 → 5
• result ^= 2 → 7
• result ^= 1 → 6
• result ^= 2 → 4

Final answer: 4

Why this is a strong interview answer

This solution is better than using a hash map because it uses:

• O(1) extra space
• One pass through the array

That’s exactly the kind of tradeoff interviewers want you to notice.

Worked example 2: Single Number II

Problem

Now every number appears three times except one, which appears once.

Example:

nums = [2, 2, 3, 2]

Answer: 3

A simple XOR no longer works because duplicates do not cancel in groups of three. You need a different idea.

Insight

Instead of tracking whole numbers, count bits at each position.

For each bit position i:

• Count how many numbers have that bit set
• Since most numbers appear three times, the total count at each bit is a multiple of 3, except for the unique number
• If count % 3 != 0, that bit belongs to the unique number

Python solution

from typing import List

def single_number_ii(nums: List[int]) -> int:
    result = 0
    for bit in range(32):
        bit_sum = 0
        for num in nums:
            bit_sum += (num >> bit) & 1
        if bit_sum % 3:
            result |= (1 << bit)

    # Handle negative numbers in 32-bit signed integer form
    if result >= 2 ** 31:
        result -= 2 ** 32
    return result

How it works

Suppose the numbers are:

[2, 2, 3, 2]

Binary representations:

• 2 = 010
• 3 = 011

Count bits position by position:

• Bit 0: 0 + 0 + 1 + 0 = 1 → 1 % 3 = 1
• Bit 1: 1 + 1 + 1 + 1 = 4 → 4 % 3 = 1
• Bit 2: 0 + 0 + 0 + 0 = 0

So the result is 011, which is 3.

A note on negative numbers

Python integers are unbounded, while many interview problems assume 32-bit signed integers. That’s why the adjustment at the end matters if the result should be negative.

If the sign bit is set, subtract 2**32 to convert from unsigned 32-bit to signed form.

Worked example 3: Counting Bits

Problem

Given an integer n, return an array ans where ans[i] is the number of 1 bits in i for 0 <= i <= n.

Example:

n = 5

Expected output:

[0, 1, 1, 2, 1, 2]

First approach: brute force

For each number, count its bits by repeatedly clearing the lowest set bit or shifting.

from typing import List

def count_bits_bruteforce(n: int) -> List[int]:
    def popcount(x: int) -> int:
        count = 0
        while x:
            x &= x - 1
            count += 1
        return count

    return [popcount(i) for i in range(n + 1)]

This is easy to understand, but it repeats work.

Better approach: dynamic programming

The pattern is:

• i >> 1 is i without its last bit
• i & 1 tells you whether the last bit is set
• So the recurrence is:

countBits(i) = countBits(i >> 1) + (i & 1)

Python solution

from typing import List

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

Step-by-step trace

For n = 5:

• ans[0] = 0
• 1: ans[1 >> 1] + (1 & 1) = ans[0] + 1 = 1
• 2: ans[1] + 0 = 1
• 3: ans[1] + 1 = 2
• 4: ans[2] + 0 = 1
• 5: ans[2] + 1 = 2

Final array:

[0, 1, 1, 2, 1, 2]

Why this recurrence is useful

This is a classic example of turning a bit problem into a DP problem. Once you notice that shifting right removes one bit, you can build answers from smaller values.

Step-by-step approach to solving bit manipulation problems

When you see a bit manipulation question in an interview, use this checklist:

1. Ask what pattern the numbers follow

Look for clues like:

• “every number appears twice”
• “all numbers appear three times except one”
• “find whether a bit is set”
• “count set bits”

These clues usually tell you which bit trick applies.

2. Decide whether you need whole numbers or individual bits

• If duplicates cancel out cleanly, XOR may solve it directly.
• If the repetition count is not 2, bit counting is often better.
• If you need to inspect one position, use a mask like 1 << bit.

3. Write the smallest possible invariant

An invariant is something that stays true as you process the input.

Examples:

• XOR of all processed numbers equals the unmatched value so far
• Bit count at each position modulo 3 determines the unique number
• ans[i] can be derived from a smaller subproblem in counting bits

4. Watch for signed integer behavior

This matters when problems involve negatives or assume fixed-width integers.

In Python, you may need to normalize results if the platform expects 32-bit signed output.

Complexity comparison

Here is a quick comparison of common approaches for the patterns above:

Common bit manipulation techniques

Check if a bit is set

Use:

if num & (1 << bit):
    # bit is set

Set a bit

Use:

num |= (1 << bit)

Clear a bit

Use:

num &= ~(1 << bit)

Toggle a bit

Use:

num ^= (1 << bit)

These operations show up constantly in interview questions involving masks, permissions, subsets, and state compression.

Related problems you should know

Once you understand these essentials, the next problems become much easier:

• Single Number
• Single Number II
• Counting Bits
• Number of 1 Bits
• Reverse Bits
• Sum of Two Integers
• Missing Number
• Power of Two
• Subsets / Bitmask enumeration
• Maximum XOR of Two Numbers in an Array

Each one uses the same core habits: reason about bits directly, look for cancellation or recurrence, and keep the implementation small.

Key takeaways

• XOR is the first tool to reach for when duplicates appear in pairs.
• If values repeat three times, count bits instead of XORing whole numbers.
• Counting bits often has a simple DP recurrence: ans[i] = ans[i >> 1] + (i & 1).
• Always think about sign handling when working in fixed-width integer problems.
• Most bit manipulation questions become easier once you stop thinking in decimal and start thinking in binary.

Practice these next

Try these problems after you finish this topic:

1. Single Number
2. Single Number II
3. Counting Bits
4. Number of 1 Bits
5. Reverse Bits

If you want to trace the XOR state, bit counts, and DP transitions step by step, I built an interactive version of this walkthrough at codebrew.ai — might help if you’re a visual learner.