Bit Manipulation for Coding Interviews: 20 Tricks and the Problems They Solve

Bit manipulation is a small topic with a reputation for being "tricky" because most explanations list magic expressions without saying why they work. Every trick in this guide follows from three facts about binary numbers, and once you see those, you can re-derive them in an interview instead of memorising them.

The guide covers the operators and their language-specific pitfalls, 20 tricks with one-line justifications, and full solutions for the problems that actually get asked: the Single Number variants, Missing Number, Counting Bits, Subsets, Reverse Bits, Sum of Two Integers and a bitmask DP example.

Binary Numbers and Two's Complement in Five Minutes

An unsigned integer is a sum of powers of two: 13 = 8 + 4 + 1 = 1101. Bit i (counting from 0 on the right) has value 2ⁱ.

Signed integers in Java, C++ and practically every machine use two's complement: for a 32-bit int, the top bit has value −2³¹ instead of +2³¹. Two consequences matter constantly:

• -x == ~x + 1. To negate, flip all bits and add one. So −1 is all ones (0xFFFFFFFF).
• Range is asymmetric: −2³¹ to 2³¹−1. Negating Integer.MIN_VALUE gives Integer.MIN_VALUE back.

The last three rows contain the two most important tricks in this whole post: x & (x−1) (12 & 11 = 8, lowest set bit cleared) and x & −x (12 & −12 = 4, lowest set bit isolated).

Bitwise Operators and Their Language Traps

Built-in popcount helpers save time: Integer.bitCount(x) and Long.bitCount in Java, __builtin_popcount / __builtin_popcountll or C++20 std::popcount in C++, x.bit_count() in Python 3.10+ (or bin(x).count("1")). Also useful: Integer.numberOfTrailingZeros, __builtin_ctz, and Python's x.bit_length(). If you are a C++ user, the C++ STL guide also covers std::bitset.

The 20 Bit Tricks You Will Actually Use

Each comes with the reason it works. If you know the reason, you will not need to memorise the expression.

Trick 19 has a simpler cousin you will use far more often in binary search: lo + (hi - lo) / 2 avoids overflow for non-negative bounds.

Single Number I, II and III: The XOR Family

Single Number (136): every element twice except one

public int singleNumber(int[] nums) {
    int x = 0;
    for (int n : nums) x ^= n;      // pairs cancel, the single value survives
    return x;
}

Dry run: [4, 1, 2, 1, 2]: 0^4 = 4 (100), ^1 = 5 (101), ^2 = 7 (111), ^1 = 6 (110), ^2 = 4 (100). Answer 4. O(n) time, O(1) space, versus O(n) space for a hash set. The interviewer wants you to mention both and explain why XOR works (commutative, associative, self-inverse).

Single Number II (137): every element three times except one

XOR no longer cancels (x ^ x ^ x = x). Think per bit instead: for each of the 32 bit positions, count how many numbers have that bit set. Triples contribute a multiple of 3; the remainder mod 3 is the single number's bit.

int singleNumber(vector<int>& nums) {
    unsigned result = 0;
    for (int b = 0; b < 32; b++) {
        int count = 0;
        for (int x : nums) count += ((unsigned)x >> b) & 1u;
        if (count % 3) result |= (1u << b);
    }
    return (int)result;             // reinterpret: handles negative answers
}

O(32n). The elegant O(n) follow-up keeps two masks, ones and twos, that together act as a per-bit counter modulo 3 (states 00 → 01 → 10 → 00):

def single_number_ii(nums):
    ones = twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos   # bits seen once (mod 3)
        twos = (twos ^ x) & ~ones   # bits seen twice (mod 3)
    return ones

Trace a single bit that is set in x three times: after the first, ones = 1, twos = 0. After the second, ones = 0 (1 ^ 1), twos = 1. After the third, ones = (0 ^ 1) & ~1 = 0, twos = (1 ^ 1) & ~0 = 0. Back to 00. A bit seen once ends with ones = 1, which is why ones is the answer. Python's unbounded integers behave like infinite two's complement, so this works for negative numbers too.

Single Number III (260): two numbers appear once

XOR all numbers to get xy = a ^ b. Since a ≠ b, xy has at least one set bit; at that bit, a and b differ. Isolate it with xy & -xy (trick 7) and split all numbers into two groups by that bit. Each group contains exactly one of a, b plus complete pairs, so XORing each group gives a and b.

public int[] singleNumberIII(int[] nums) {
    int xy = 0;
    for (int n : nums) xy ^= n;
    int diff = xy & -xy;                 // lowest bit where a and b differ
    int a = 0, b = 0;
    for (int n : nums) {
        if ((n & diff) == 0) a ^= n;
        else b ^= n;
    }
    return new int[]{a, b};
}

Edge case worth naming: if xy is Integer.MIN_VALUE, then -xy overflows back to itself, and xy & -xy is still Integer.MIN_VALUE, which is the correct isolated bit. In Python there is no overflow at all.

Missing Number, Duplicates and XOR Over Ranges

Missing Number (268)

Array of n distinct numbers from [0, n], one missing. XOR all indices 0..n and all values; everything present cancels, leaving the missing number. The sum formula n(n+1)/2 − sum also works but can overflow in fixed-width languages for large n; XOR cannot.

def missing_number(nums):
    x = len(nums)                        # include n itself
    for i, v in enumerate(nums):
        x ^= i ^ v
    return x

XOR of a range in O(1)

XOR of 1..n follows a period-4 pattern: n % 4 == 0 → n, 1 → 1, 2 → n + 1, 3 → 0. Check: 1^2^3 = 0 (n = 3), 1^2^3^4 = 4 (n = 4). XOR of a range [l, r] is f(r) ^ f(l − 1), the same prefix idea as prefix sums. This solves XOR Operation in an Array (1486) variants and many "XOR queries on a subarray" problems (1310) when combined with a prefix XOR array.

Set Mismatch (645) and Find the Duplicate

When one number is duplicated and one is missing, XOR of indices and values gives dup ^ missing; split by the lowest set bit exactly as in Single Number III, then check which of the two candidates appears in the array.

Counting Bits: Hamming Weight, Counting Bits DP, Hamming Distance

Number of 1 Bits (191): Brian Kernighan's algorithm

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;        // drop the lowest set bit
        count++;
    }
    return count;          // loop runs once per set bit, works for negative n too
}

The naive loop while (n != 0) { count += n & 1; n >>= 1; } never terminates in Java for negative n because >> keeps copying the sign bit. Use >>> there, or Kernighan's version, which is immune.

Counting Bits (338): bits for every number 0..n in O(n)

vector<int> countBits(int n) {
    vector<int> bits(n + 1, 0);
    for (int i = 1; i <= n; i++)
        bits[i] = bits[i >> 1] + (i & 1);    // or: bits[i & (i - 1)] + 1
    return bits;
}

Both recurrences are DP on bit structure: i >> 1 is i without its last bit, and i & (i − 1) is i without its lowest set bit. Dry run to n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2. Output [0,1,1,2,1,2].

Hamming Distance (461) and Total Hamming Distance (477)

Distance between x and y is popcount(x ^ y), since XOR marks differing bits. For the sum over all pairs, do not compare pairs (O(n²)): for each bit position, if k numbers have the bit set, it contributes k × (n − k) differing pairs. Total O(32n). This per-bit counting idea recurs across bit problems.

Subsets via Bitmask: Enumerating and Iterating Submasks

A set of n ≤ ~20 items fits in one integer: bit i set means item i is present. Set operations become single instructions: union a | b, intersection a & b, difference a & ~b, membership (a >> i) & 1, size popcount(a).

Subsets (78), iteratively

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

public List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> sub = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if (((mask >> i) & 1) == 1) sub.add(nums[i]);
        res.add(sub);
    }
    return res;
}

For [a, b, c]: mask 0 = 000 → [], 1 = 001 → [a], 2 = 010 → [b], 3 = 011 → [a, b], ..., 7 = 111 → [a, b, c]. O(n · 2ⁿ), same as the recursive version in the backtracking guide, with no recursion. Use backtracking when you need pruning; use masks when you need to index subsets (for DP or meet-in-the-middle).

Iterating all submasks of a mask

// visits every non-empty submask of m in decreasing order
for (int s = m; s > 0; s = (s - 1) & m) {
    // process submask s
}
// iterating submasks of every mask in [0, 2^n) costs O(3^n) in total

Why 3ⁿ: each element is in one of three states relative to (mask, submask): not in mask, in mask but not submask, in both. That bound is what makes "DP over subsets of subsets" feasible for n ≤ ~15.

Maximum Product of Word Lengths (318)

A neat practical use: encode each word's letters as a 26-bit mask. Two words share no letters iff mask1 & mask2 == 0, an O(1) check instead of comparing strings. O(n² + total characters).

Bitmask DP: When the State Is a Set

When a DP needs to remember which items have been used (not just how many), and n is small, the mask is the state. Classic shapes:

• Travelling salesman / Shortest Path Visiting All Nodes (847): state (mask of visited nodes, current node). O(2ⁿ · n²) for TSP; BFS over (mask, node) for unweighted 847.
• Assignment problems: assign n workers to n jobs; state is the mask of taken jobs, and the worker index is popcount(mask). O(2ⁿ · n).
• Partition to K Equal Sum Subsets (698), Parallel Courses II (1494), Smallest Sufficient Team (1125).

def min_assignment_cost(cost):
    n = len(cost)
    INF = float("inf")
    dp = [INF] * (1 << n)
    dp[0] = 0
    for mask in range(1 << n):
        if dp[mask] == INF:
            continue
        worker = bin(mask).count("1")       # next worker to assign
        if worker == n:
            continue
        for job in range(n):
            if not mask >> job & 1:
                nxt = mask | (1 << job)
                dp[nxt] = min(dp[nxt], dp[mask] + cost[worker][job])
    return dp[(1 << n) - 1]

Rule of thumb: 2²⁰ ≈ 10⁶ masks is comfortable, 2²⁰ × 20 ≈ 2 × 10⁷ transitions is fine in C++/Java and borderline in Python. If n is around 40, think meet-in-the-middle (split into two halves of 2²⁰). The constraint "n ≤ 15" or "n ≤ 20" in a problem statement is almost always a hint for bitmasks. More DP patterns are in the DP interview guide.

Arithmetic with Bits: Sum of Two Integers, Reverse Bits, Divide

Sum of Two Integers (371) without + or −

public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;   // positions that generate a carry
        a = a ^ b;                   // add without carry
        b = carry;                   // add the carries in the next round
    }
    return a;
}

Each round moves carries one position left, so it terminates within 32 rounds in Java (carries shift out of the 32-bit int). In Python, carries on negative numbers never shift out because integers are unbounded, so you must mask with 0xFFFFFFFF each round and convert the result back: if a > 0x7FFFFFFF, return ~(a ^ 0xFFFFFFFF). Explaining this difference is a good signal of real understanding.

Reverse Bits (190)

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1);  // append n's lowest bit to res
        n >>>= 1;                     // logical shift: no sign smearing
    }
    return res;
}

Follow-up: "called millions of times?" Cache the reversal of each byte in a 256-entry table and combine four lookups, or use the divide-and-conquer swap (swap 16-bit halves, then 8-bit groups, then 4, 2, 1 with masks like 0x55555555). That masks trick is also how hardware-free popcount works.

Divide Two Integers (29)

Without multiplication or division, subtract the largest divisor << k that fits, add 1 << k to the quotient, repeat: O(log² n) or O(log n) with care. The real test is overflow handling: Integer.MIN_VALUE / -1 must return Integer.MAX_VALUE, and working in negative numbers (which have the larger range) avoids most overflow bugs.

Gray code (89)

The i-th Gray code is i ^ (i >> 1). Consecutive values differ in exactly one bit. One line, but explaining why (each increment of i changes the trailing bits, and XOR with the shifted value leaves exactly one changed bit) is what interviewers ask.

How Bit Manipulation Shows Up in Interviews

In Indian interview loops, bit questions show up most in campus placements, online assessments and phone screens (Single Number, Power of Two, Counting Bits), and in embedded/systems roles at companies such as Qualcomm, Samsung, NVIDIA and Texas Instruments, where register-level manipulation is part of the job. At product companies they more often appear inside harder problems as bitmask state. Process details vary by team; confirm with your recruiter.

Bit tricks also connect to number theory: modular exponentiation by squaring reads the exponent bit by bit, and sieve implementations use bitsets to save memory. The math and number theory guide covers those.

Common Bit Manipulation Mistakes

• Operator precedence: x & 1 == 0 in Java/C++ is x & (1 == 0) (and a compile error in Java). Parenthesise every bit expression.
• Overflowing shifts: 1 << 31 is negative, 1 << 40 on an int is wrong. Use long literals.
• Arithmetic right shift on negatives causing infinite loops. Use >>> in Java, unsigned types in C++.
• Assuming 32-bit behaviour in Python. Mask explicitly.
• XOR swap on the same variable (a ^= a zeroes it), e.g. swapping arr[i] and arr[j] when i == j.
• Using bitmasks for n > 30 in an int, or for n too large for 2ⁿ states at all.
• Forgetting x > 0 in the power-of-two check: 0 & (−1) == 0 would wrongly return true.

Bit Manipulation Practice List

Problem 15 uses a binary trie, explained in the trie data structure guide. Problem 14 is a nice closing exercise: the AND of every number in [l, r] keeps only the common binary prefix of l and r, found by shifting both right until they are equal (or by repeatedly applying r &= r − 1 while r > l).

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.