Bit Manipulation Interview Questions: 15 Tricks and Patterns

Bit manipulation interview questions test whether you can solve problems by operating directly on the binary representation of integers using AND, OR, XOR, NOT, and shifts. Nearly all of them reduce to about fifteen reusable tricks, such as x & (x - 1) to clear the lowest set bit and a ^ a = 0 to cancel pairs. Learn those tricks in binary, and problems like Single Number, Counting Bits, and Subsets become short, predictable code.

This guide gives you the trick table, a binary walkthrough for each important one, and the interview problems each trick solves.

Key Takeaways

• Fifteen operations cover most bit manipulation interview questions. Memorize them as pictures in binary, not as formulas.
• x & (x - 1) clears the lowest set bit and x & -x isolates it. These two expressions drive counting, power-of-two checks, and Single Number III.
• XOR is the pair-cancelling operator. If a problem says "every element appears twice except one," reach for XOR first.
• Bitmasks turn subsets of up to about 20 items into integers, which makes subset enumeration and bitmask DP possible.
• Language matters: Python has no fixed width, Java and JavaScript have >>>, and in C, C++, Java, and JavaScript x & 1 == 0 does not mean what you think.

What Are Bitwise Operators?

Bitwise operators are operators that act on each bit of an integer independently, instead of on the number as a whole. There are six you need for interviews.

Two more ideas make everything else click.

Bit positions count from the right, starting at 0. In 1100 (12), bits 2 and 3 are set. 1 << i builds a number with only bit i set, which is how you target a single position.

Negative numbers use two's complement. To negate x, flip all bits and add 1. So -x equals ~x + 1, and that identity is the reason x & -x works. In 8 bits, 12 is 00001100 and -12 is 11110100.

If you want the bigger picture of where bit tricks sit among other techniques, the coding interview patterns cheat sheet covers all the major patterns side by side.

The 15 Essential Bit Tricks Table

This is the core of the guide. Each row lists the expression, what it does, a binary example, and the problems it typically solves.

Once you see x & (x - 1) as "remove the rightmost 1," a whole group of problems stops being puzzles.

Walkthrough: why x & (x - 1) clears the lowest set bit

Take x = 12.

x       = 1100
x - 1   = 1011   (the lowest 1 becomes 0, the zeros below it become 1)
x & x-1 = 1000   (the tail cancels, higher bits survive)

Subtracting 1 always flips the lowest 1 and everything below it. AND keeps only bits that are 1 in both, so that whole tail disappears. A power of two has exactly one set bit, so removing it gives 0. That is the entire proof behind trick 8.

Walkthrough: why x & -x isolates the lowest set bit

x       = 00001100   (12)
~x      = 11110011
-x      = 11110100   (~x + 1)
x & -x  = 00000100   (4)

Adding 1 to ~x carries through its trailing ones and stops exactly at x's lowest set bit. Above that position, x and -x are opposites, so only the lowest set bit survives the AND.

Walkthrough: enumerating submasks

Starting from sub = mask = 1011 and applying sub = (sub - 1) & mask until it reaches 0 gives 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000. Subtracting 1 moves to the next smaller number, and ANDing with the mask drops any bits outside the mask. Running this for every mask of n bits costs O(3^n) in total, which is a useful number to quote when you explain complexity. The Big O notation cheat sheet covers why exponential bounds like 2^n and 3^n are acceptable only for small n.

XOR Patterns Interviewers Love

XOR is the operator that returns 1 when two bits differ and 0 when they match. Its useful properties are that it is commutative, associative, self-inverse (a ^ a = 0), and has 0 as its identity. Those four facts generate most XOR interview questions.

Pattern 1: cancel the pairs

Single Number (LeetCode 136) gives an array where every element appears twice except one.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

Every pair XORs to 0, and the order does not matter, so only the unpaired value remains. O(n) time, O(1) space.

Pattern 2: XOR indices against values

Missing Number (LeetCode 268) asks for the one number missing from 0 to n. XOR every index and every value together, plus n. Each present number appears twice and cancels, so the result is the missing one. Find the Difference (LeetCode 389) is the same idea applied to characters.

Pattern 3: split by a differing bit

Single Number III (LeetCode 260) has two unpaired values. XOR of the whole array gives a ^ b, which is nonzero because a and b differ. Its lowest set bit marks a position where a and b disagree, so you split the array into two groups by that bit and XOR each group.

def single_number_iii(nums):
    diff = 0
    for n in nums:
        diff ^= n
    low = diff & -diff
    a = 0
    for n in nums:
        if n & low:
            a ^= n
    return [a, diff ^ a]

This combines trick 10 and trick 7, which is exactly why the table is worth learning.

Pattern 4: prefix XOR

Prefix XOR works like prefix sums. If p[i] is the XOR of the first i elements, then the XOR of the range from i to j is p[j + 1] ^ p[i]. XOR Queries of a Subarray (LeetCode 1310) and Count Triplets That Can Form Two Arrays of Equal XOR (LeetCode 1442) are direct applications.

A related move is using a parity mask as a hash map key. In Find the Longest Substring Containing Vowels in Even Counts (LeetCode 1371), you toggle one bit per vowel and look for the earliest index with the same mask.

Pattern 5: XOR with a trie

Maximum XOR of Two Numbers in an Array (LeetCode 421) inserts each number into a binary trie from the highest bit down, then greedily walks the opposite branch for every bit. It is the hardest common XOR problem and a good test of whether you can combine data structures with bit reasoning.

Bit problems are where interviews often stall: you know an O(1) space trick exists, but under pressure the exact expression will not come back. Our guide on what to do when stuck in a coding interview covers how to recover out loud without losing the round.

Counting and Isolating Bits

Counting set bits, also called population count or Hamming weight, is one of the most asked bit manipulation interview questions. There are three approaches worth knowing.

Shift and check. Test the lowest bit, shift right, repeat. This runs once per bit position, so 32 iterations for a 32-bit integer.

Kernighan's algorithm. Repeatedly clear the lowest set bit. It loops once per set bit, which is faster for sparse numbers.

def count_bits(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

Built-ins. Most languages ship a popcount (see the gotchas section), but be ready to write Kernighan's loop by hand.

Counting Bits for every number

Counting Bits (LeetCode 338) asks for the bit count of every number from 0 to n. Calling a popcount n times works, but the expected answer is a one-line DP.

def count_bits_range(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

Shifting right drops the lowest bit, so the count of i equals the count of i >> 1 plus that dropped bit. An equally valid recurrence is dp[i] = dp[i & (i - 1)] + 1. If you want more practice building recurrences like this, the dynamic programming patterns guide walks through the standard families.

Other counting and isolating problems

• Hamming Distance (461): count set bits of x ^ y. XOR marks every differing position.
• Total Hamming Distance (477): for each bit position, count how many numbers have it set (k). That position contributes k * (n - k).
• Reverse Bits (190): read bit i with trick 1 and write it into position 31 - i.
• Bitwise AND of Numbers Range (201): the answer is the common binary prefix of left and right. Shift both right until equal, then shift back.
• Single Number II (137): every value appears three times except one. Count how many numbers have each bit set and take the count modulo 3.

Bitmasks for Subsets

A bitmask is an integer where bit i represents whether item i is included in a set. With n items, the integers 0 through 2^n - 1 represent every possible subset exactly once.

Generating all subsets

Subsets (LeetCode 78) has a clean bitmask solution that avoids recursion entirely.

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

This is O(n * 2^n), the same as backtracking. The recursion and backtracking guide covers the recursive alternative and when it handles pruning better.

Bitmasks as fast sets

When the universe is small, such as 26 lowercase letters, a mask replaces a hash set. Maximum Product of Word Lengths (LeetCode 318) builds one 26-bit mask per word, then two words share no letters exactly when mask_a & mask_b == 0. Maximum Length of a Concatenated String with Unique Characters (LeetCode 1239) uses the same idea.

Bitmask DP

Bitmask DP is dynamic programming where part of the state is a bitmask recording which items have been used. It works when n is small, usually 20 or fewer, because 2^20 is about one million states.

Shortest Path Visiting All Nodes (LeetCode 847) is the classic example. The state is (current node, visited mask). BFS starts from every node with only its own bit set, each move ORs in the neighbor's bit, and the answer is the first distance at which the mask equals (1 << n) - 1.

Other bitmask DP problems to know:

• Partition to K Equal Sum Subsets (698): state is the mask of used numbers.
• Smallest Sufficient Team (1125): state is the mask of covered skills.
• Travelling salesman style problems: dp[mask][last] is the cheapest way to visit the cities in mask and end at last.

The recognition signal is a tiny constraint like n <= 12, n <= 16, or n <= 20 paired with "visit all," "assign each," or "cover every."

Language-Specific Gotchas

Bit tricks are language-agnostic, but most bugs in bit rounds come from language details. If you have not picked one yet, see which language to use in a coding interview.

Operator precedence

In C, C++, Java, and JavaScript, &, ^, and | bind more loosely than ==. So x & 1 == 0 parses as x & (1 == 0), which is wrong. Always write (x & 1) == 0. Python is the exception: comparison operators bind more loosely than bitwise ones, so the expression behaves as intended there. Parentheses are free, so use them everywhere.

Python and Sum of Two Integers

Sum of Two Integers (LeetCode 371) asks you to add without +. The standard loop computes carry with a & b and the partial sum with a ^ b. In Java or C++ it terminates because the carry eventually shifts off the top of a 32-bit integer. In Python it can loop forever on negative inputs, because there is no top. The fix is to simulate 32 bits.

def get_sum(a, b):
    mask = 0xFFFFFFFF
    while b & mask:
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)

The last line converts a 32-bit pattern with bit 31 set back into a negative Python integer. Expect a follow-up question about this if you interview in Python; the Python interview questions guide covers related integer behavior.

Right shift on negatives

Arithmetic right shift keeps the sign bit, so -8 >> 1 is -4 in Python, Java, and JavaScript, and in C++20 and later. It rounds toward negative infinity, which differs from integer division in Java and C++ for odd negatives: -7 >> 1 is -4, while -7 / 2 is -3. In Python, -7 // 2 is also -4, so the two agree there.

Bit Manipulation Practice Problems

Work through these in order: easy problems build the tricks, mediums combine them, and hards embed them in larger algorithms.

Five of these (Sum of Two Integers, Number of 1 Bits, Counting Bits, Missing Number, Reverse Bits) make up the binary section of the Blind 75 list. If you are choosing between curated lists, our comparison of Blind 75 vs NeetCode 150 vs Grind 75 explains how much bit practice each one includes.

How to practice

1. Draw the binary. For every new problem, write out two or three small inputs in 4 or 8 bits before coding.
2. Name the trick out loud. Saying "I'll clear the lowest set bit with x and x minus one" shows the interviewer you know why it works. The guide on how to think out loud in a coding interview has phrasing that helps here.
3. Test negatives and zero. Most bit bugs hide in 0, -1, and the minimum integer.

Bit manipulation rarely fills an entire interview, but it often decides whether your answer uses O(1) space or fits the time limit. Learn the fifteen tricks as binary pictures and most of these problems become routine.