Bit Manipulation Problems — Signed Shift Traps & XOR Tricks

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));
    }
}

Power of Two Check: Beyond the Obvious

A number is a power of two if it has exactly one bit set in its binary representation. The expression n & (n - 1) == 0 directly verifies that. But there's a subtlety: 0 also satisfies (0 & -1) == 0, so you must include the n > 0 guard.

Beyond the standard check, interviewers may ask variations: "Is n a power of 4?" — here you combine the power-of-two check with a bit mask that isolates the parity of the set bit position: (n & 0x55555555) != 0 for 32-bit integers.

package io.thecodeforge.bit;

public class PowerOfTwo {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    public boolean isPowerOfFour(int n) {
        // Must be power of two and the set bit at an even position (0-indexed)
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
    }

    public static void main(String[] args) {
        PowerOfTwo checker = new PowerOfTwo();
        System.out.println("Is 8 power of two? " + checker.isPowerOfTwo(8));
        System.out.println("Is 16 power of four? " + checker.isPowerOfFour(16));
    }
}

Isolating the Rightmost Set Bit: n & -n

The expression n & -n isolates the lowest set bit of an integer. How does it work? Two's complement negation inverts all bits and adds one. So -n = ~n + 1. ANDing with n zeroes out everything except the rightmost 1-bit. This is crucial for Fenwick trees (Binary Indexed Trees) and for grouping elements based on the last differing bit.

Example: n = 12 (1100), -n = -12 (0100 in two's complement, limited to lower bits). n & -n = 0100 = 4, which is the value of the lowest set bit.

package io.thecodeforge.bit;

public class LowestSetBit {
    public int isolateLowestSetBit(int n) {
        if (n == 0) throw new IllegalArgumentException("No set bit in zero");
        return n & -n;
    }

    public static void main(String[] args) {
        LowestSetBit bitUtil = new LowestSetBit();
        System.out.println("Lowest set bit of 12 (1100) is: " + bitUtil.isolateLowestSetBit(12));
        System.out.println("Lowest set bit of -8 is: " + bitUtil.isolateLowestSetBit(-8));
    }
}

Bitmasking: Enumerate All Subsets in O(2^n)

For problems like "generate all subsets" (LeetCode 78), a bitmask represents which elements are included. Each integer from 0 to (1 << n) - 1 maps to a unique subset. The j-th bit being 1 means the j-th element is in the subset. This is an $O(2^n * n)$ approach (or $O(2^n)$ if you process each subset directly).

The bitmask method is impressively compact: one loop over mask and inner loop over bits. Interviewers love it because it shows you understand binary representation and space efficiency — no recursion overhead.

package io.thecodeforge.bit;

import java.util.ArrayList;
import java.util.List;

public class SubsetEnumerator {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        int totalSubsets = 1 << n; // 2^n
        for (int mask = 0; mask < totalSubsets; mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }

    public static void main(String[] args) {
        SubsetEnumerator enumerator = new SubsetEnumerator();
        int[] input = {1, 2, 3};
        System.out.println(enumerator.subsets(input));
    }
}