Bit Manipulation Tricks for Coding Interviews

Bit manipulation has a reputation as the “party trick” section of coding interviews — and that reputation is deserved. The problems look intimidating, the optimal solutions look like magic, and yet the entire topic rests on about six tricks you can learn in an afternoon.

This post covers why bit manipulation keeps showing up in interviews, the six tricks that solve the vast majority of bitwise questions, and five classic problems with worked Python solutions. If you want the structured version, Day 53 of our challenge covers these techniques as part of the full 60-day curriculum.

Why Interviewers Ask Bit Manipulation Questions

Three reasons, roughly in order of importance:

1. It separates memorizers from understanders. You can’t pattern-match your way through n & (n - 1) — you either understand what it does to the binary representation or you don’t.
2. It tests low-level fluency. Companies working on systems, embedded software, compression, networking, or graphics genuinely use these operations daily. A candidate who is comfortable at the bit level signals depth.
3. The optimal solutions are dramatic. Many bitwise problems have an obvious O(n) space solution and a stunning O(1) space solution. Interviewers love questions with that gap because the follow-up (“can you do it without extra memory?”) reveals how you think under pressure.

The Operators, in 30 Seconds

Python gives you six bitwise operators:

1a & b    # AND: 1 where both bits are 1
2a | b    # OR: 1 where either bit is 1
3a ^ b    # XOR: 1 where bits differ
4~a       # NOT: flips every bit (in Python: ~a == -a - 1)
5a << k   # left shift: multiply by 2**k
6a >> k   # right shift: floor-divide by 2**k

Here’s what they do to actual bits:

1    a = 12   ->  1100          a = 12   ->  1100
2    b = 10   ->  1010          b = 10   ->  1010
3    ------------------         ------------------
4    a & b    ->  1000  (8)     a | b    ->  1110  (14)
5    a ^ b    ->  0110  (6)     a << 1   ->  11000 (24)

With those in hand, let’s build the toolkit.

The 6 Essential Tricks

Trick 1: Check the k-th Bit — n & (1 << k)

Shift a 1 into position k, AND it with n. Non-zero means the bit is set.

1    n        =  1 0 1 1 0 1   (45)
2    1 << 2   =  0 0 0 1 0 0
3    ---------------------- &
4    result   =  0 0 0 1 0 0   -> bit 2 is set

1def is_bit_set(n, k):
2    return (n & (1 << k)) != 0
3
4print(is_bit_set(45, 2))  # True  (45 = 0b101101)
5print(is_bit_set(45, 1))  # False

The same mask sets a bit with OR (n | (1 << k)), clears it with AND-NOT (n & ~(1 << k)), and toggles it with XOR (n ^ (1 << k)).

Trick 2: Clear the Lowest Set Bit — n & (n - 1)

Subtracting 1 flips the lowest set bit to 0 and every bit below it to 1. ANDing with the original wipes them all out:

1    n        =  1 0 1 1 0 0   (44)
2    n - 1    =  1 0 1 0 1 1   (43)
3    ---------------------- &
4    result   =  1 0 1 0 0 0   (40)  -> lowest set bit removed

This one trick powers population counts, power-of-two checks, and subset enumeration. Kernighan’s bit-counting algorithm is just this trick in a loop:

1def count_set_bits(n):
2    count = 0
3    while n:
4        n &= n - 1   # drop the lowest set bit
5        count += 1
6    return count
7
8print(count_set_bits(44))  # 3

It runs in O(number of set bits), not O(number of total bits).

Trick 3: XOR Cancels Itself — x ^ x == 0

XOR is the interviewer’s favorite operator because of three properties:

• x ^ x == 0 (a value cancels itself)
• x ^ 0 == x (zero is the identity)
• XOR is commutative and associative (order doesn’t matter)

XOR every element of a list together and all the paired values annihilate, leaving whatever appears an odd number of times. Three of the five problems below are built on this.

1result = 0
2for x in [4, 1, 2, 1, 2]:
3    result ^= x
4print(result)  # 4 — the pairs cancelled out

Trick 4: Power of Two Check — n & (n - 1) == 0

A power of two has exactly one set bit. Clear the lowest set bit (Trick 2) and a power of two becomes zero:

1    n = 16   ->  1 0 0 0 0        n = 18  ->  1 0 0 1 0
2    n - 1    ->  0 1 1 1 1        n - 1   ->  1 0 0 0 1
3    -------------------- &        ------------------- &
4    result   ->  0 0 0 0 0  ✓     result  ->  1 0 0 0 0  ✗

1def is_power_of_two(n):
2    return n > 0 and (n & (n - 1)) == 0

Don’t forget the n > 0 guard — zero and negatives would otherwise slip through.

Trick 5: Swap Without a Temp Variable — Triple XOR

1a, b = 5, 9
2a ^= b
3b ^= a   # b = b ^ (a ^ b) = a
4a ^= b   # a = (a ^ b) ^ a = b
5print(a, b)  # 9 5

In Python you’d write a, b = b, a, obviously. But the XOR swap is a classic warm-up question because explaining why it works proves you’ve internalized Trick 3.

Trick 6: Multiply and Divide by Powers of Two — Shifts

1n = 13
2print(n << 3)   # 104  (13 * 8)
3print(n >> 1)   # 6    (13 // 2)

1    13       =  0 0 0 1 1 0 1
2    13 << 3  =  1 1 0 1 0 0 0   (104)

You’ll rarely shift for “performance” in Python, but shifts are the idiomatic way to build masks (1 << k), walk bits (n >>= 1), and enumerate all 2^n subsets of a set — a technique we use to generate the power set on Day 54.

5 Classic Interview Problems

Problem 1: Single Number

Every element in a list appears twice except one. Find it in O(n) time and O(1) space.

The O(n) space answer uses a hash map. The O(1) answer is pure Trick 3:

1def single_number(nums):
2    result = 0
3    for num in nums:
4        result ^= num
5    return result
6
7print(single_number([4, 1, 2, 1, 2]))  # 4

All pairs cancel; the lone element survives. Time O(n), space O(1).

Problem 2: Counting Bits

For every integer i from 0 to n, return how many 1-bits it has.

You could run Kernighan’s loop (Trick 2) on each number for O(n log n) total. The DP insight gets you to O(n): i & (i - 1) has exactly one fewer set bit than i, and it’s smaller than i, so its answer is already computed.

1def count_bits(n):
2    ans = [0] * (n + 1)
3    for i in range(1, n + 1):
4        ans[i] = ans[i & (i - 1)] + 1
5    return ans
6
7print(count_bits(5))  # [0, 1, 1, 2, 1, 2]

Time O(n), space O(n) for the output. We dig into this problem on Day 55: Counting Bits.

Problem 3: Missing Number

A list contains n distinct numbers from the range [0, n]. Find the missing one.

XOR every index and every value together. Each present number appears twice (once as an index, once as a value) and cancels; the missing number appears once, as an index only.

1def missing_number(nums):
2    result = len(nums)          # the index n itself
3    for i, num in enumerate(nums):
4        result ^= i ^ num
5    return result
6
7print(missing_number([3, 0, 1]))  # 2

Time O(n), space O(1) — and no overflow concerns, unlike the sum-formula approach in fixed-width languages.

Problem 4: Power of Two

Determine whether an integer is a power of two — without loops.

Straight application of Trick 4:

1def is_power_of_two(n):
2    return n > 0 and (n & (n - 1)) == 0
3
4print(is_power_of_two(64))  # True
5print(is_power_of_two(96))  # False

Time O(1), space O(1). The follow-up “power of four?” adds one mask: the single set bit must sit at an even position, so also check n & 0x55555555 != 0.

Problem 5: Reverse Bits

Reverse the 32 bits of an unsigned integer.

Build the result bit by bit: peel the lowest bit off the input, push it onto the output.

1def reverse_bits(n):
2    result = 0
3    for _ in range(32):
4        result = (result << 1) | (n & 1)
5        n >>= 1
6    return result
7
8print(bin(reverse_bits(0b00000000000000000000000000000101)))
9# 0b10100000000000000000000000000000

1    input:   ... 0 0 0 1 0 1      output so far
2    step 1:  take 1  ->            1
3    step 2:  take 0  ->            1 0
4    step 3:  take 1  ->            1 0 1
5    ... 29 more shifts pad the right with zeros

Time O(1) — always exactly 32 iterations — space O(1).

Cheat Table: When to Reach for Which Trick

Keep Going

Bit manipulation rewards deliberate, spaced practice more than almost any other interview topic — the tricks are few, but they must be automatic. In our 60-day challenge, Day 53 builds the technique foundation, Day 54 applies bitmasking to subset generation, and Day 55 goes deep on the counting-bits DP. Sign up free and take them on — by day 55 these problems will feel routine.

Related Articles

• The Data Structures Cheatsheet
• Tries Explained Simply (With Real Interview Problems)
• Hashing and Hash Functions: Efficient Data Retrieval

Happy coding, and may all your bits be exactly where you expect them!