Bit Manipulation Cheat Sheet: Every Formula You Need for Interviews

You know bit manipulation is on the problem. The variable names say "mask" and "bits." You write n & (n - 1) and then stare at it wondering if you had the right trick or the other one.

That is the whole trap. Not the problem on the screen. There are a dozen tricks, they look almost identical, and under pressure they blur together into a single anxiety spiral.

This bit manipulation cheat sheet is the reference. Read it once the morning of. Scan it when you draw a blank. Bookmark it and pretend you'll review it more carefully later (you won't, but the illusion helps).

Six Operators Drive Every Bit Problem

Before the tricks, the foundation. If you can't read these fluently, the rest won't click.

Operator	Symbol	Effect
AND	`&`	1 only if both bits are 1
OR	`\|`	1 if either bit is 1
XOR	`^`	1 if bits differ, 0 if the same
NOT	`~`	Flips every bit
Left shift	`<<`	Multiply by 2^k
Right shift	`>>`	Divide by 2^k (floor for negatives)

XOR is the most useful operator for interview problems. AND extracts bits, OR sets bits, XOR detects differences and cancels duplicates. If a bit manipulation problem has an elegant O(1) solution, XOR is probably involved somehow.

One more thing that will save you at 2am: in two's complement, ~n == -(n + 1). That means -n == ~n + 1. You will use this. It will look like magic until the Two's Complement section below, and then it will look like arithmetic.

Ten Tricks Worth Knowing Cold

These are the operations that recur. Learn what each one does, not just the formula. Writing the formula without understanding it is how you get halfway through an interview and forget which one clears the bit vs isolates it.

Check if bit k is set

(n >> k) & 1   # returns exactly 0 or 1
n & (1 << k)   # returns 0 or 2^k (truthy, not strictly 1)

The first form is cleaner for boolean checks. Shift n right k places so the target bit lands in position 0, then mask it.

Set bit k

n | (1 << k)

OR with a mask that has only bit k set. Every other bit is unchanged.

Clear bit k

n & ~(1 << k)

~(1 << k) is all 1s except position k. AND keeps everything else intact and zeros out bit k.

Toggle bit k

n ^ (1 << k)

XOR flips a bit if the mask bit is 1, leaves it alone if 0. Use it to flip exactly one position.

Check even or odd

n & 1   # 1 = odd, 0 = even

Faster than n % 2 and identical in meaning. The last bit determines parity. You will feel disproportionately pleased every time you use this.

Check if n is a power of 2

n > 0 and (n & (n - 1)) == 0

Powers of 2 have exactly one set bit. Subtracting 1 flips that bit and sets all lower bits to 1. AND produces 0. The n > 0 guard handles the edge case where n = 0, which would pass the bitmask check and then quietly embarrass you.

Clear the lowest set bit

n & (n - 1)

This removes the rightmost 1-bit. Use it in a loop to count set bits (Brian Kernighan's algorithm): each iteration strips one bit and increments a counter. Runs in O(popcount(n)), not O(bit width). The name "Brian Kernighan" is worth mentioning out loud in the interview.

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

Isolate the lowest set bit

n & (-n)

This gives you only the rightmost 1-bit, as a power of 2. It works because -n == ~n + 1 in two's complement: flipping all bits and adding 1 makes every higher bit the opposite while the lowest set bit and everything below it cancel out to leave just that one bit. This sounds like nonsense until you trace through it once with a concrete number.

Build a mask of k ones

(1 << k) - 1

Shift 1 into position k, then subtract 1 to fill all lower bits with 1s. (1 << 4) - 1 gives 0b1111, a 4-bit all-ones mask. Standard for isolating the lower k bits of a number: n & ((1 << k) - 1).

XOR cancellation

a ^ a == 0   # any value XORed with itself is 0
a ^ 0 == a   # any value XORed with 0 is itself

XOR is commutative and associative. These two facts underlie the single-number problem: XOR all elements together, and every duplicate pair cancels out, leaving only the unpaired element. One pass, no extra space, and the interviewer nods.

Two's Complement Is Why Half These Tricks Work

Understanding ~n = -(n + 1) is the key to reading bit tricks without second-guessing yourself. It follows from how two's complement represents negative numbers: flip all bits and add 1 to negate.

So:

~0 = -1 (all bits set is negative 1)
~n = -(n + 1) always
-n = ~n + 1

The "isolate lowest set bit" trick (n & (-n)) depends entirely on this. So does "clear lowest set bit" (n & (n - 1)). Once you see those as consequences of two's complement rather than arbitrary formulas, they stop feeling like black magic and start feeling like high school algebra that just happens to involve binary.

Everyone skips this section when they're studying. They pay for it in the interview when someone asks why n & (n - 1) actually works.

For more on the mechanics, see What Is Two's Complement?.

Language Differences That Bite You

The tricks above are universal. The behavior in specific languages is not, and this is where the fun starts.

Python integers have arbitrary precision, which means no overflow ever, but it also means you have to enforce 32-bit bounds yourself. ~n always equals -(n + 1). If a problem specifies "assume 32-bit integer," mask the result manually: result & 0xFFFFFFFF. The >>> operator does not exist in Python. Python is playing a different game from everyone else.

Java: >> is arithmetic right shift (copies the sign bit). >>> is logical right shift (fills with zeros, treating the value as unsigned). This matters for negative numbers. To shift into 64-bit range safely, use 1L << 32 rather than 1 << 32. Java's decision to have two right-shift operators while Python has zero is the kind of thing that feels intentional until you have to explain which one you meant.

C++: Right shift on signed integers is implementation-defined by the standard, though every major compiler (gcc, clang, MSVC) uses arithmetic shift in practice. For portable code, cast to unsigned before right-shifting. 1 << 32 on a 32-bit int is undefined behavior. Use 1LL << 32. Undefined behavior in C++ doesn't mean "it crashes." It means "it works on your laptop, works in staging, and then does something baffling in production at 3am."

Apache Ant build log showing "compiled on December 17 1969", a signed integer underflow from a corrupted timestamp that rolled back past the Unix epoch

When integer overflow or underflow goes unchecked, time itself becomes optional.

For authoritative C++ shift semantics, see the cppreference arithmetic operators reference. Java's >> vs >>> distinction is defined precisely in the Java Language Specification, section 15.19.

Three Patterns You Will See in Problems

The tricks above are building blocks. Here's how they combine.

Single unique element (XOR sweep)

XOR every element in the array together. Pairs cancel (a ^ a = 0). The unique element survives. One pass, O(1) space.

This extends to "two unique elements": XOR everything to get a ^ b, find any set bit using x & (-x), partition the array on that bit, XOR each partition separately. The two groups separate a and b because they differ at that bit.

Subset enumeration

To iterate over all 2^n subsets of n elements, loop from 0 to 2^n - 1. Each integer is a bitmask where bit k set means element k is included.

n = len(elements)
for mask in range(1 << n):
    subset = [elements[k] for k in range(n) if mask & (1 << k)]
    process(subset)

To enumerate only the subsets of a given mask m (not all 2^n subsets):

s = m
while s > 0:
    process(s)
    s = (s - 1) & m
# handle the empty subset (s = 0) separately if needed

Bitmask DP problems use this pattern constantly. State that encodes "which elements have been used" is the clearest sign you need it. The bitmask article covers this in more detail.

Bit counting

Built-in popcount is faster than manual loops. Use it when you can:

Python: bin(n).count('1') or n.bit_count() (Python 3.10+)
Java: Integer.bitCount(n)
C++: __builtin_popcount(n) or std::popcount(n) (C++20)

For problems that need the sum of popcount values across a range (0 to n), a DP approach runs in O(n): dp[i] = dp[i >> 1] + (i & 1). Each number's count is one more or the same as the number with its last bit dropped.

Bit Manipulation Cheat Sheet: Have These Cold

n & (n - 1) clears the lowest set bit. n & (-n) isolates it.
(1 << k) - 1 is a mask of k ones.
Check power of 2: n > 0 and (n & (n - 1)) == 0.
XOR every element together to find the unpaired one. Pairs cancel to 0.
In Python, mask to 32 bits manually when the problem specifies 32-bit integers: result & 0xFFFFFFFF.
In Java, use >>> for logical right shift on negative numbers. In C++, shift unsigned types.
Build habits around the four single-bit operations (check, set, clear, toggle) and the rest follows from there.

Bit manipulation rewards fluency more than creativity. The hard part is recognizing which trick applies, not executing it. That comes from working problems out loud: naming the operation before you write the code, explaining why n & (n - 1) drops the lowest bit instead of just writing it and hoping. SpaceComplexity puts you through bit manipulation problems in a realistic voice interview, scores your solution and your reasoning, and flags when you're writing correct code without explaining why it works.

To put these tricks to work on actual problems, Bit Manipulation Isn't Magic. It's Five Patterns. covers the problem archetypes, and 14 Bit Manipulation Problems to Master for Coding Interviews walks through the full set from easy to hard.