Bit Manipulation Interview Problems: Patterns, Tricks & Gotchas

Every major tech company — Google, Meta, Amazon — consistently includes at least one bit manipulation problem in their coding rounds. That's not a coincidence. These problems test whether you understand how a CPU actually works at its lowest level, separating candidates who memorized patterns from those who genuinely understand computation. A single XOR or a bitwise AND can replace entire loops, cut memory usage in half, and run in constant time — and interviewers know it.

The core challenge with bit manipulation isn't the operators themselves — you likely know & | ^ ~ << >>. The challenge is pattern recognition: seeing a problem about finding a missing number or detecting duplicates and immediately knowing 'this is an XOR problem.' Without that pattern library wired into your brain, you'll stare at the problem and reach for a HashSet when a two-line XOR solution was sitting right there.

By the end of this article you'll have five rock-solid bit manipulation patterns locked in with real runnable code, you'll understand exactly why each trick works at the binary level (not just that it works), and you'll know the specific gotchas that cause smart engineers to get these wrong under interview pressure — things like signed integer overflow, arithmetic vs. logical right shifts, and why Brian Kernighan's bit-counting trick is faster than a naive loop.

The Power of XOR: Solving 'Single Number' (LeetCode 136)

The XOR (exclusive OR) operator is the 'magic wand' of bit manipulation. Its properties are unique: any number XORed with itself is 0 ($A \oplus A = 0$), and any number XORed with 0 is itself ($A \oplus 0 = A$). It is also commutative and associative.

In an interview, if you see a problem where every element appears twice except for one, don't reach for a Map or a Set. That's $O(n)$ space. By XORing every number in the array together, all pairs cancel each other out, leaving only the unique element. This is the gold standard for efficiency: $O(n)$ time and $O(1)$ space.

package io.thecodeforge.bit;

public class XorUniqueFinder {
    /**
     * Finds the element that appears only once in an array where
     * every other element appears exactly twice.
     */
    public int singleNumber(int[] nums) {
        int uniqueElement = 0;
        for (int currentNum : nums) {
            // XOR operation effectively 'cancels' out pairs
            uniqueElement ^= currentNum;
        }
        return uniqueElement;
    }

    public static void main(String[] args) {
        XorUniqueFinder finder = new XorUniqueFinder();
        int[] input = {4, 1, 2, 1, 2};
        System.out.println("The single number is: " + finder.singleNumber(input));
    }
}

Counting Set Bits: Brian Kernighan’s Algorithm (LeetCode 191)

Interviewers often ask for the 'Hamming Weight' or the number of set bits (1s) in an integer. A naive approach checks every bit one by one ($O(32)$). However, Brian Kernighan’s algorithm is much faster because it only iterates as many times as there are set bits.

The trick lies in the expression n & (n - 1). This operation always flips the least significant (rightmost) set bit to zero. By repeating this until the number becomes zero, you count the bits in record time.

package io.thecodeforge.bit;

public class BitCounter {
    /**
     * Counts the number of set bits (1s) in an integer.
     * Efficiency: O(k) where k is the number of set bits.
     */
    public int countSetBits(int inputNumber) {
        int count = 0;
        while (inputNumber != 0) {
            // This clears the least significant set bit
            inputNumber &= (inputNumber - 1);
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        BitCounter counter = new BitCounter();
        // Binary for 7 is 0111 (3 bits)
        System.out.println("Set bits in 7: " + counter.countSetBits(7));
    }
}

Frequently Asked Questions