Bit Manipulation for Coding Interviews: The Tricks Worth Knowing

Most placement candidates spend weeks memorizing dynamic programming templates while ignoring bit manipulation entirely, only to panic when an interviewer asks for an $O(1)$ space solution. You do not need to memorize thirty different bitwise properties because interviewers loop through the exact same five core patterns every time. Focus entirely on XOR cancellation, bit checking via shifts, Brian Kernighan's bit reduction, powers of two, and subset generation through bitmasks.

XOR cancellation

The caret operator cancels identical bits when you apply it twice, which turns a linear search into a constant space operation. Take the array [4, 1, 2, 1, 2]. If you compute 4 ^ 1 ^ 2 ^ 1 ^ 2, the duplicate ones and twos eliminate each other because 1 ^ 1 becomes 0. You are left with 4 ^ 0 ^ 0, which evaluates directly to 4. This works because XOR is commutative and associative. When a problem asks for the single non-repeating element among pairs, run a single pass with a variable initialized to zero and accumulate the XOR sum.

Checking and setting bits

Computers store integers in binary, and you can query any position by shifting a 1 left by k places. To check if the third bit of the number 5 (which is 101 in binary) is active, evaluate 5 & (1 << 2). The mask 1 << 2 produces 4 (100 in binary). The bitwise AND operation 5 & 4 yields 4, which is non-zero, confirming the bit is set. To turn a specific bit on without changing the others, use the bitwise OR operator like n | (1 << k). To turn that same bit off, combine a left shift with a bitwise NOT and an AND, such as n & ~(1 << k).

Counting set bits

Interviewers frequently ask how many ones exist in the binary representation of a number like 13. If you write a loop that checks every bit using n >> i & 1 thirty-two times, your solution scales with the fixed bit-width of the integer rather than the value itself. Instead, use Brian Kernighan's algorithm with the expression n & (n - 1).

Here is how that subtraction works by hand for n = 12 (1100 in binary):

• First iteration: n = 12 (1100), n - 1 = 11 (1011). 12 & 11 evaluates to 8 (1000). Count becomes 1.
• Second iteration: n = 8 (1000), n - 1 = 7 (0111). 8 & 7 evaluates to 0 (0000). Count becomes 2.
• Third iteration: n = 0, loop terminates.

The operation n & (n - 1) drops only the rightmost set bit in a single step, meaning the loop runs exactly as many times as there are ones in the binary string.

Powers of two and subset bitmasks

A number is an exact power of two if and only if its binary form contains a single set bit, which makes the check n > 0 && (n & (n - 1)) == 0 completely reliable for inputs like 16 or 1024. For generating subsets, treat an integer from 0 to (1 << n) - 1 as a binary selection mask. If you have three items in an array, the numbers from 0 to 7 represent every possible inclusion combination, where the k-th bit tells you whether to pick the element at index k.

Bit Manipulation Rule of Thumb:

• Use n ^ n = 0 to pair and cancel duplicates.
• Use n & (n - 1) to clear the lowest set bit.
• Use n & (1 << k) to test if index k is active.
• Use 1 << n to iterate through $2^n$ subsets.

Open DSA Tracker and sort problems by the bit manipulation tag to practice these four patterns on real interview questions today.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Dynamic programming on Wikipedia.