LiveCodingInterview.com
← Articles

Bit Manipulation Interview Questions: When XOR Beats a Loop

A bit manipulation interview question is one where the fastest or lowest-memory solution comes from operating directly on the binary representation of a number, using AND, OR, XOR, NOT, and the two shift operators instead of a hash map, a sorted copy, or an extra array. You recognize the pattern from a constraint that rules out the obvious data structure, usually phrased as "constant extra space" or "O(1) space," paired with a task that maps naturally onto binary: finding a value that appears once, checking a numeric property like a power of two, or enumerating every combination of a small set. The rest of this guide covers which operators and tricks account for most real problems, the actual time complexity behind them, the mistakes that cost candidates points, and what to say out loud while you work through one.

How Do You Recognize a Bit Manipulation Interview Question?

You recognize a bit manipulation question from two things showing up together in the prompt: a constraint that rules out the obvious hash map or extra array, and a task that maps naturally onto a number's binary representation rather than its decimal value. Neither signal alone is reliable, since plenty of O(1) space problems are really about in-place swapping or two pointers instead. It's the combination that points you toward bits.

A handful of phrases tend to appear in the same sentence as a genuine bit manipulation problem:

  • "Find the number that appears exactly once" or "find the missing number" in an array where everything else appears twice or in a known range, a strong signal for the XOR-cancellation trick.
  • "In O(1) space" or "without using extra memory," paired with a task over an array of small integers, ruling out a hash set as the intended answer.
  • "Power of two," "power of four," or "count the number of set bits," which are direct asks about a number's binary form rather than its value.
  • "Enumerate every subset" or "every combination" of a set with a small item count, usually under twenty or so, a candidate for representing each subset as an integer bitmask.
  • Flags, permissions, or several boolean settings packed into a single integer, a design cue toward masking rather than a business-logic explanation.

Once you see one of these signals, say the pattern out loud before you start coding. Naming it early keeps you from reaching for a hash map out of habit when the constraint has already ruled it out.

What Bitwise Operators Do You Need to Know Cold?

Every bit manipulation solution is built from five operators: AND, OR, XOR, NOT, and the two shifts, left and right. AND returns a 1 only where both operands have a 1, which is why it's used to check or clear specific bits. OR returns a 1 where either operand has a 1, which is why it's used to set a bit without disturbing the others. XOR returns a 1 exactly where the two operands differ, the property behind both toggling a bit and canceling out a duplicate value. NOT flips every bit, and the two shifts move all the bits of a number left or right by a given count, which doubles or halves the value for each position shifted, ignoring the bits that fall off the end.

a = 0b1010  # 10
b = 0b0110  # 6

a & b   # 0b0010 -> 2, bits set in both
a | b   # 0b1110 -> 14, bits set in either
a ^ b   # 0b1100 -> 12, bits set in exactly one
~a      # -11, Python's arbitrary-precision two's complement
a << 1  # 0b10100 -> 20, shift left, doubles the value
a >> 1  # 0b0101 -> 5, shift right, halves it and drops the remainder

Memorize what each one does, not just the symbol, because interview problems rarely ask you to name an operator. They ask you to check whether a specific bit is on, so you need to already know that AND with a mask does that job before you can write the line.

Which Bit Tricks Actually Show Up in Interviews?

A small set of tricks accounts for most bit manipulation problems you'll actually see: reading, setting, clearing, or toggling one specific bit using a mask built from a single shifted 1, checking whether a number is a power of two, counting how many bits are set, and finding a single non-duplicate value in a list with XOR. Learn these five and you can cover the large majority of what shows up in a loop.

The mask-based operations follow a fixed shape once you've written each one a couple of times:

  • n & (1 << i) checks whether bit i is set, returning a nonzero value if it is.
  • n | (1 << i) sets bit i to 1 without touching any other bit.
  • n & ~(1 << i) clears bit i to 0 without touching any other bit.
  • n ^ (1 << i) toggles bit i, flipping it whichever way it currently sits.
  • n & (n - 1) clears the lowest set bit, the operation behind both the power-of-two check and Brian Kernighan's bit-counting trick below.

Subtracting 1 from a number flips every bit from the lowest set bit downward, so ANDing the original number with that result clears exactly the lowest 1. A power of two has exactly one set bit, so clearing it always leaves zero, which gives you the one-line check n & (n - 1) == 0 for any n greater than zero. Run that same clearing step in a loop and you get a way to count set bits that only iterates once per bit that's actually on, instead of once per bit position in the whole number.

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1  # clears the lowest set bit each pass
        count += 1
    return count


def find_single_number(nums):
    result = 0
    for num in nums:
        result ^= num  # every value that appears twice cancels itself out
    return result

The single-number trick works because XOR is commutative and associative, so the order of the values doesn't matter, and because any value XORed with itself is zero while any value XORed with zero is itself. Line up every number in the list and the pairs collapse to zero, leaving only the one that never found a partner. That's an O(n) time, O(1) space answer to a problem that looks like it needs a hash set to track what you've already seen.

How Do You Use a Bitmask to Represent a Subset?

A bitmask represents a subset of n items as a single integer with n bits, where bit i being set means item i is included in that subset. Looping an integer from 0 up to 2 raised to the n power, minus 1, walks through every possible subset without ever building one explicitly until you need it, which is why bitmasks show up constantly in problems that ask you to consider every combination of a small set.

def all_subsets(items):
    n = len(items)
    for mask in range(1 << n):
        subset = [items[i] for i in range(n) if mask & (1 << i)]
        yield subset

This is the same idea behind the state-space exploration in a backtracking solution, except a bitmask replaces the recursive call stack with a single integer you can compare, store in a set, or use as a dictionary key. That last property is what makes bitmasks the backbone of a specific style of dynamic programming problem, often called bitmask DP, where the DP state includes which subset of items has already been used, like assigning tasks to workers or finding the smallest team that covers every required skill. The dynamic programming patterns guide covers how to recognize a DP problem in general; a bitmask DP problem adds one extra signal on top of those, a small n, usually under twenty or so, since building a table indexed by every possible subset costs O(2^n) space before you've even started filling it in.

What Is the Real Time and Space Complexity of a Bit Manipulation Solution?

Most answers claim a bitwise operation runs in O(1) and stop there, and that claim is true, but only relative to the value of the number, not to its size in bits. A single AND, OR, XOR, or shift on a fixed-width integer, 32 or 64 bits on most hardware, executes in one processor step, so calling it O(1) is accurate. A solution that inspects every bit of a number, like the set-bit counting loop above, is a different claim: it runs proportional to the number of bits actually set, so it's really O(b) for bit width b, or O(log n) expressed in terms of the value n instead.

That distinction matters because Python complicates the fixed-width assumption most other languages rely on. A Java or C++ int is always the same width, so a shift or a mask always operates over that fixed size and any bit that shifts past the top just disappears. Python integers grow to fit whatever value they hold, so a left shift on a very large number allocates more space as it grows. Interviewers rarely probe this directly, but if asked to defend an O(1) claim, the honest answer names the fixed-width assumption behind it instead of repeating "O(1)" without qualification.

What Mistakes Sink a Bit Manipulation Answer in an Interview?

The most common mistake is misreading a "constant extra space" constraint as an automatic signal for bit manipulation when it sometimes points somewhere else entirely, like the in-place two-pointer swapping covered in the sliding window guide's comparison of the two patterns. Check whether the task maps onto a numeric or binary property before committing to a bit-based solution just because the space constraint fits.

Negative numbers cause a second, more specific class of bugs. Two's complement representation means a right shift on a negative number in most languages preserves the sign bit, so it doesn't behave like plain division the way it does for positive numbers, and Java draws a hard line between its two right-shift operators, a sign-preserving one and an unsigned one, that Python and C++ don't offer. If your solution is only tested against positive values, say out loud that you're assuming nonnegative input.

Fixed-width overflow trips up the same candidates from the opposite direction. Code practiced in Python, where integers never overflow, can silently rely on that property and then fail once translated to Java or C++ during a live pair-programming round, where a 32-bit int wraps around once a shift pushes it past the boundary. If your practice happens mostly in Python, trace through what a mask-based solution does once capped at 32 bits, so the fixed-width version doesn't surprise you live.

What Should You Say Out Loud While You Solve a Bit Manipulation Problem?

Name the recognition signal first, the same way you would for any other pattern: point at the space constraint and the binary-shaped task in the same sentence, and say plainly that this looks like a bit manipulation problem before you touch the keyboard. That single sentence tells the interviewer you matched the pattern deliberately instead of guessing your way there.

State which specific trick you're reaching for and why, rather than jumping straight to code. If you're building a mask, say what the mask represents in plain terms, a specific bit position or a set of allowed flags, before you write the shift expression that builds it. Trace a small example by hand, ideally a four-bit number you can track completely in your head, before you generalize to the full solution, since a mask expression that looks right can still have an off-by-one in the shift amount that only shows up once you walk through actual bits.

Once the code is on the screen, state the complexity claim explicitly and be ready to defend the nuance from earlier in this guide if the interviewer pushes on it. Saying "this bitwise operation is O(1) because it runs on a fixed-width integer, but the loop around it is O(b) for the number of bits" reads as a candidate who actually understands what they wrote, not one repeating a memorized answer.

Which Practice Problems Actually Build the Pattern-Recognition Skill?

A small, ordered set of problems builds real recognition skill faster than grinding through dozens of loosely related ones, since each one forces you to notice a signal before you start coding rather than pattern-matching from memory.

  • Single Number, the canonical case for the XOR-cancellation trick covered above, and the fastest way to internalize why order doesn't matter to XOR.
  • Number of 1 Bits, a direct application of the Brian Kernighan counting loop, worth timing yourself on until the n &= n - 1 step is automatic.
  • Power of Two, where the one-line n & (n - 1) == 0 check is easy to write and easy to get subtly wrong, so test it by hand against zero and a negative input before trusting it.
  • Subsets, the cleanest bitmask enumeration exercise, and a good check on whether you can map n items to n bits without hesitating over the indexing.
  • Counting Bits, which forces you to notice the recurrence between the bit count of a number and the bit count of that number shifted right by one, a genuine dynamic programming relationship hiding inside what looks like a pure bit manipulation problem.

Our curated question bank draws from real onsite reports rather than an unfiltered public archive, so the specific problems you find under bit manipulation reflect what's actually being asked in current loops, not a static list that stopped updating years ago.

Where Bit Manipulation Fits Into Your Broader Pattern Prep

Bit manipulation is a narrower pattern than most of the others in a typical interview loop, but it rewards preparation more than most, since the tricks are few, fixed, and reused across dozens of different-looking problems once you know them. Our guide to spotting patterns before you code covers how bit manipulation fits alongside the broader set you'll actually need, and the same signal-recognition habit applies to every other pattern on that list.

If the complexity argument here felt unfamiliar, especially the split between a fixed-width O(1) operation and an O(b) loop over a variable number of bits, our breakdown of how to analyze time complexity covers that kind of bit-width reasoning in more depth, including how interviewers probe a complexity claim with a follow-up question. And if a bitmask DP problem brought you here, the dynamic programming patterns guide linked above is the place to go next, since bitmask DP is ordinary DP with a subset as the state, once you already know what a bitmask represents.

Frequently Asked Questions

What is bit manipulation in coding interviews?

Bit manipulation is a technique for solving problems by operating directly on a number's binary representation with operators like AND, OR, XOR, and bit shifts, instead of using a hash map, a sorted copy, or an extra array. It's the intended approach whenever a problem rules out extra memory and the task maps naturally onto a number's binary form.

Are bit manipulation interview questions common in real loops?

They come up less often than array, string, or graph problems, but a handful of specific tricks, XOR-cancellation, the power-of-two check, and bitmask enumeration, appear often enough across different companies that skipping them entirely leaves a real gap. Bit manipulation interview questions also show up as a smaller part of a harder problem, like a bitmask DP question, more often than as the whole problem on their own.

What's the fastest way to check if a number is a power of two?

Use n & (n - 1) == 0 for any n greater than zero. Subtracting 1 flips every bit below the lowest set bit, so ANDing that result with the original number clears the lowest set bit, and a power of two has only one set bit to begin with, so the result is always zero.

Does Python's arbitrary-precision integer change how bit manipulation questions work?

Yes, in a way worth knowing even though it rarely gets tested directly. A Java or C++ int has a fixed width, so a shift or mask always operates over the same number of bits and any bit that shifts past the top disappears. Python integers grow as needed, so a left shift on a very large number keeps costing more as the number grows, rather than staying a fixed, constant-time operation.

What's the difference between bit manipulation and bitmask dynamic programming?

Bit manipulation is the set of operators and tricks themselves, AND, OR, XOR, shifts, and the masks built from them. Bitmask dynamic programming is a specific style of DP problem that uses a bitmask as part of the DP state to represent which items from a small set have already been used, combining the bit manipulation toolkit with ordinary DP transitions.

How do I practice bit manipulation interview questions without grinding hundreds of problems?

Work through a small ordered set instead: Single Number for XOR, Number of 1 Bits for the counting trick, Power of Two for the mask check, and Subsets for bitmask enumeration. Those four cover the recognition signals behind most bit manipulation interview questions you'll actually see, and going deeper into bitmask DP only makes sense once those four feel automatic.