Bit Manipulation

1The mental model (what this really is)#

An integer is a fixed row of switches, nothing more.

• A 32-bit int is 32 switches, a 64-bit long is 64. Each switch (a bit) is 0 or 1.
• Place values go right to left: 1, 2, 4, 8, 16, and so on. That is just base 2.
• So 13 is 1101: one 8, one 4, zero 2s, one 1.

Bit manipulation means working the switches directly instead of treating the number as one value. You flip them, test them, shift them left and right, and combine two rows with logical operators.

Four operators do almost all the work:

• & (AND): a bit is 1 only if both inputs are 1. Tests a bit or clears bits. 1101 & 0100 = 0100.
• | (OR): a bit is 1 if either input is 1. Sets bits. 1101 | 0010 = 1111.
• ^ (XOR): a bit is 1 if the inputs differ. The magic one. Toggles, pairs, and cancels. 1101 ^ 0110 = 1011.
• ~ (NOT): flips every bit. ~0000 = 1111 within the width you are working in.

Two shifts move whole rows:

• x << k multiplies by 2 to the power k (pushes bits left, fills zeros on the right). 1 << 4 is 16.
• x >> k divides by 2 to the power k (pushes bits right). 48 >> 2 is 12.

2How to recognize it (the signals in a problem)#

You are looking at a bit problem the moment you see one of these cues. Interviewers rarely say "bits," so train on the phrasing instead.

• Numbers appearing an even or odd number of times, or "every element appears twice except one." That is XOR, almost always.
• A small fixed set (roughly up to 20 or 32 items) where you track which ones are used. A 32-bit int is a free set of 32 flags. The giveaway is a constraint line like 1 <= n <= 20.
• "Count set bits," "find a power of two," "swap without a temp," or "add without +, -, *, /." That phrasing is an explicit invitation.
• Numbers near a power of two, or ranges like 0 to 2^n, where binary structure matters.
• "Enumerate all subsets of a set." Loop an integer from 0 to 2^n and read its bits.
• "Can you do this in O(1) space" right after you gave a hashmap answer. Nine times out of ten they want XOR.

3The template (how it works, with pseudocode)#

Keep these building blocks in muscle memory. I rewrite them from scratch on scratch paper before every interview, because they are easy to fumble under pressure and a wrong & versus | silently returns garbage with no error.

# Read the i-th bit (0 = rightmost)
bit = (x >> i) & 1

# Set the i-th bit to 1
x = x | (1 << i)

# Clear the i-th bit to 0
x = x & ~(1 << i)

# Toggle the i-th bit
x = x ^ (1 << i)

# Check if a number is a power of two (and not zero)
is_power = x > 0 and (x & (x - 1)) == 0

# Turn off the lowest set bit
x = x & (x - 1)

# Isolate the lowest set bit
lowest = x & (-x)

# Count set bits (Brian Kernighan: loops once per set bit)
count = 0
while x:
    x = x & (x - 1)
    count += 1

Two of these deserve a pause.

• x & (x - 1) clears the lowest 1 bit. Subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into 1, so AND-ing wipes that whole low section down to the next 1. Example: 12 = 1100, 11 = 1011, and 1100 & 1011 = 1000. The lowest 1 is gone.
• x & (-x) isolates the lowest 1. In two's complement, -x is the bit-flip of x plus 1, which lines up exactly at that lowest bit and nowhere else. For 12, x & (-x) gives 100, which is 4, the value of that lowest set bit.

For subset enumeration, the frame is:

for mask in range(0, 1 << n):   # every possible subset of n items, 2^n of them
    for i in range(n):
        if (mask >> i) & 1:      # item i is in this subset
            # use item i

• The outer loop runs 2^n times, once per subset.
• The inner loop reads each of the n bits to see which items the current mask includes.
• For n = 20 that is about a million masks, which runs comfortably.
• For n = 30 it is a billion and you are already in trouble, which is exactly why the constraint on n is your signal.

4A worked example (walk through one problem step by step)#

Classic prompt: given an array where every number appears exactly twice except for one number that appears once, find the single number. Linear time, constant extra space.

• My first instinct as a beginner was a hashmap counting occurrences. That works, it is O(n) time, but it uses O(n) space, and the "constant space" hint is screaming that there is something cleaner.
• The key observation: we want pairs to disappear and the loner to survive. XOR does exactly that. Any value XOR'd with itself is 0.
• So if I XOR every element together, each pair cancels to 0, and the one unpaired value is left standing.

Run it on [4, 1, 2, 1, 2], starting with an accumulator ans = 0:

• ans = 0 ^ 4 = 4. In bits, 0000 XOR 0100 is 0100.
• ans = 4 ^ 1 = 5. 0100 XOR 0001 is 0101.
• ans = 5 ^ 2 = 7. 0101 XOR 0010 is 0111.
• ans = 7 ^ 1 = 6. 0111 XOR 0001 is 0110. The first 1 just got cancelled.
• ans = 6 ^ 2 = 4. 0110 XOR 0010 is 0100. The first 2 just got cancelled.

Final answer: 4. The two 1s cancelled each other, the two 2s cancelled each other, and 4 stood alone.

Why order did not matter:

• XOR is commutative and associative, so a ^ b = b ^ a and the grouping is free.
• Shuffle that array any way you like and the pairs still find each other and vanish.
• That property is why this works in one pass with a single variable, no sorting required.

ans = 0
for num in array:
    ans = ans ^ num
return ans

One pass, one integer of memory. Deliver this after first naming the hashmap version and you show you know both and chose the better one on purpose. That reads as judgment, not luck, and judgment is what the round is grading.

Name the hashmap, then beat it with XOR. Knowing both is the signal; picking the better one is the point.

5Variations and gotchas#

Once you own the single-number idea, interviewers twist it:

• Every number twice except two singles. XOR everything to get a ^ b. That combined value has a 1 in every bit position where a and b differ. Isolate any one of those differing bits with diff & (-diff), then split the array into two groups by whether each element has that bit set, and XOR each group separately. a lands in one group, b in the other, each surviving alone. This is Single Number III.
• Every number three times except one. XOR no longer works, because three copies of a value do not cancel to zero. Instead, count bits per position across all numbers; each position's count mod 3 reconstructs the answer bit by bit. Or use two accumulators (ones and twos) that simulate counting mod 3 in a single pass.
• Bitmask dynamic programming. Problems like assigning n tasks to n people, or the traveling salesman on a small graph, use an integer mask to represent "which items are used so far." The state is dp[mask], and you transition by setting one more bit. This is where bit manipulation meets DP, and it is the home of the hard problems on this topic.
• Swap two values with no temp: a ^= b; b ^= a; a ^= b. Cute, rarely needed, breaks if a and b are the same memory location, good to know it exists.

Gotchas that bite people:

• Signed integers and the sign bit. In 32-bit and 64-bit languages the top bit means negative. Right-shifting a negative number may copy the sign bit (arithmetic shift) instead of filling zeros, so -8 >> 1 is not what a naive reader expects. In Java use >>> for an unsigned shift that fills zeros. In Python integers are arbitrary precision, so there is no fixed 32-bit wrap unless you mask with & 0xFFFFFFFF.
• Operator precedence. x & 1 == 0 does NOT mean what you think. == binds tighter than &, so this parses as x & (1 == 0), which is x & 0, which is always 0. Always parenthesize: (x & 1) == 0. I have watched strong candidates lose ten minutes chasing this exact bug on a whiteboard.
• 1 << i overflow. For large i in a fixed-width language, shift a 64-bit literal, not a 32-bit int. In Java write 1L << 40, not 1 << 40, or you get silent garbage once i hits 31.

6Complexity#

Single-pass bit solutions are the whole selling point over the hashmap.

• Most are O(n) time and O(1) space, where n is the array length. That O(1) space is the win, so say it out loud.
• Operations on a single integer (test, set, shift, Kernighan's count) are O(w) where w is the word width, usually 32 or 64. Since w is a fixed constant, people call these O(1).
• Kernighan's set-bit count runs once per set bit, so it is O(number of set bits), which beats checking all 32 positions when the number is sparse.

Subset and bitmask work is exponential by nature, and that is fine when n is small.

• Subset enumeration is O(2^n) just to list the subsets, times another factor for whatever you do inside each one.
• Bitmask DP is typically O(2^n * n) or O(2^n * n^2).
• These only work because n is tiny, usually at most 20 or so (2^20 is about a million states).
• That small constraint on n is your signal to reach for a mask instead of a hashset of visited states.

7Mistakes that cost people the round#

• Forcing bits where a hashmap is cleaner. No count, subset, or binary structure means XOR is not the answer. Do not look clever at the cost of a working solution before the clock runs out.
• The precedence bug above. Parenthesize every bit expression. Say it out loud as you write it: "x and one, close paren, equals zero."
• Fumbling the templates. Mixing up set versus clear, or writing x | (1 << i) when you meant to clear with x & ~(1 << i). Drill these until they are automatic. An interviewer loses faith fast when the basics wobble, because it signals you memorized rather than understood.
• Ignoring the sign bit and overflow. Know your language's shift behavior cold. In Java or C++, mention unsigned shift and 64-bit literals before they have to ask.
• Not explaining why XOR works. Writing the one-liner is not enough. Say "pairs cancel because a XOR a is zero, so only the unpaired value survives." That one sentence is most of the interview. Skipping it makes you look like you memorized a trick off a cheat sheet.
• Off-by-one in masks. Items are indexed 0 to n-1, and the subset loop goes 0 to 2^n - 1. Mixing those bounds up corrupts the whole enumeration and is painful to spot after the fact.

8Your practice path (named problems by difficulty)#

Do them in this order. The early ones build the reflexes the later ones assume. I would not touch the Hard tier until the Easy list feels boring.

Warm-up (Easy):

• Number of 1 Bits
• Single Number
• Power of Two
• Reverse Bits
• Counting Bits
• Hamming Distance
• Complement of Base 10 Integer

Core (Medium):

• Single Number II (every element three times except one)
• Single Number III (two unique elements)
• Sum of Two Integers (add without + or -)
• Bitwise AND of Numbers Range
• Subsets (enumerate with bitmasks)
• Maximum XOR of Two Numbers in an Array
• Gray Code
• Divide Two Integers

Stretch (Hard, bitmask DP):

• Partition to K Equal Sum Subsets
• Shortest Path Visiting All Nodes
• Minimum Cost to Connect Two Groups of Points
• Maximum Students Taking Exam

If you only have one evening, do Single Number, Number of 1 Bits, Counting Bits, Subsets, and Single Number III. Those five cover the ideas behind most of the rest: XOR cancellation, Kernighan counting, DP over bit counts, mask enumeration, and the split-by-differing-bit trick.

9Where this shows up (which companies and rounds lean on it)#

Bit tricks live in the quick-filter rounds.

• They show up most in phone screens and early onsite rounds, especially at companies that love clean micro-optimizations: Amazon, Google, Microsoft, Apple, and the trading and systems firms where bits map to real hardware.
• The XOR single-number family is a perennial warm-up you should expect to see cold.
• Bitmask DP tends to appear in harder onsite rounds at Google and competitive-programming-flavored teams, where a problem reads like TSP on eight nodes.
• Embedded, graphics, and low-level systems roles use set, clear, and test bits as everyday bread and butter, so expect them throughout those interviews even when the rest of the loop is standard.

The pattern rarely carries a whole interview on its own. More often it is the elegant twist on a larger problem, or the O(1)-space upgrade an interviewer nudges you toward after your first hashmap answer. Recognizing that nudge, and reaching for XOR the moment you hear "constant space," is the real skill this topic is testing.

Want to see which companies lean on bit tricks and in which rounds? Check the company guides to map this pattern to real interview loops.