LeetPrep

Bit Manipulation in Python: Interview Tricks Explained

By Published 7 min read

Bit manipulation has a reputation for being clever tricks you either know or do not. In practice, interviews reuse about half a dozen of them, and each one is a single line once you see what the operator does to the binary digits. This guide is organised as a toolbox: the operators first, then the tricks in the order they tend to appear, then the one place where Python behaves differently from C and breaks otherwise correct code.

Every line of output below is from a real run. The helper functions were also checked against simpler versions on thousands of random inputs: 5,000 for popcount, 5,000 for the 32-bit addition and 2,000 for the triple-counting trick.

The operators on one screen

5 & 3   = 1      # AND: 1 only where both bits are 1
5 | 3   = 7      # OR:  1 where either bit is 1
5 ^ 3   = 6      # XOR: 1 where the bits differ
~5      = -6     # NOT: flips every bit, which is -(x + 1)
5 << 2  = 20     # shift left:  multiply by 2**2
20 >> 2 = 5      # shift right: floor-divide by 2**2

Two helpers make this readable while you practise: bin(10) gives '0b1010', and format(10, '08b') pads to a fixed width, giving '00001010'. For XOR remember just three facts: x ^ x = 0, x ^ 0 = x, and the order does not matter. Almost every XOR trick below comes from those three.

Trick 1: is it a power of two?

A power of two has exactly one bit set. Subtracting 1 flips that bit to 0 and every bit below it to 1, so ANDing the two numbers gives 0 if and only if there was only one set bit.

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

[is_pow2(x) for x in (1, 2, 3, 16, 0, -8)]   # -> [True, True, False, True, False, False]

The n > 0 guard matters, because 0 would otherwise pass. The same idea tests powers of four: also require the single bit to sit in an even position, using the mask 0x55555555. For (1, 4, 8, 16, 64, 32) it returned True, True, False, True, True, False.

Trick 2: clear the lowest set bit

n & (n - 1) removes the rightmost 1. For 40 (0b101000) it gives 0b100000. Repeat until the number reaches 0 and you have counted the set bits, with a loop that runs once per 1 rather than once per bit.

def popcount(n):
    c = 0
    while n:
        n &= n - 1
        c += 1
    return c

popcount(0b101101)   # -> 4   (same as bin(...).count('1') and (...).bit_count())

In real code, int.bit_count() (Python 3.10 and later) is the one-liner. In an interview, write the loop and mention the built-in. The mirror image is the lowest set bit itself: n & -n, which gave 4 for 12 and 8 for 40.

Trick 3: XOR cancels pairs

XOR every number in a list where each value appears twice except one. Pairs cancel to zero and the survivor remains. No dictionary, no sorting, O(1) memory.

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

single_number([4, 1, 2, 1, 2])   # -> 4

Missing Number uses the same cancellation. XOR the indices 0 to n with every value, and the one index with no matching value is left over:

def missing_number(nums):
    x = len(nums)
    for i, n in enumerate(nums):
        x ^= i ^ n
    return x

missing_number([3, 0, 1])                    # -> 2
missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1])  # -> 8

The hash-map version of the first problem is the pattern from the Two Sum walkthrough. XOR is its zero-memory cousin.

Trick 4: single number when everything else appears three times

Pair cancellation breaks when values repeat three times, so track each bit position modulo 3 with two variables. ones holds bits seen once (mod 3), twos holds bits seen twice, and a bit seen a third time is cleared from both.

def single_number_ii(nums):
    ones = twos = 0
    for n in nums:
        ones = (ones ^ n) & ~twos
        twos = (twos ^ n) & ~ones
    return ones

single_number_ii([2, 2, 3, 2])             # -> 3
single_number_ii([0, 1, 0, 1, 0, 1, 99])   # -> 99

If you cannot derive this live, say so and offer the counting alternative: sum each bit position across all numbers and take it modulo 3. It is slower but easy to justify, and honest reasoning beats a half-remembered formula.

Trick 5: counting bits for every number up to n

Shifting right by one drops the last bit, so the count for i equals the count for i >> 1 plus that dropped bit. That is a tiny dynamic-programming table, in the spirit of the DP for beginners guide.

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

count_bits(8)   # -> [0, 1, 1, 2, 1, 2, 2, 3, 1]

Trick 6: all subsets with a bitmask

A set of n items has 2n subsets, and each subset is just an n-bit number where bit i says whether item i is chosen. Loop over every number and read the bits.

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

subsets([1, 2, 3])
# -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

The recursion-based version is in the backtracking guide. Masks are shorter, but they only work when n is small, since 2n grows quickly. They also underpin bitmask dynamic programming, where a mask records which items were already used.

Python is not C: negative numbers

In C a 32-bit integer wraps around. Python integers never overflow, and a negative number behaves as if it had infinitely many leading 1 bits. You can see it by masking to a fixed width: (-10) & 0xFF gives 246, which is 11110110, the 8-bit two’s complement of −10. Shifts follow the same rule, rounding toward negative infinity:

-5 >> 1    # -> -3     (not -2)
 5 >> 1    # -> 2
-1 >> 10   # -> -1    (the infinite run of 1s never runs out)

Sum of Two Integers without + or –

XOR adds without carrying, and AND shifted left gives the carry. Repeat until no carry is left. In C that finishes by itself. In Python, adding -1 and 1 never finishes, because the carry keeps rippling through the infinite 1s. In the test, get_sum_wrong(-1, 1) had to be killed by a timeout. The fix is to cut everything down to 32 bits and then convert back to a negative number if the sign bit is set:

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

get_sum(1, 2)     # -> 3
get_sum(-1, 1)    # -> 0
get_sum(-5, 3)    # -> -2
get_sum(-2, -3)   # -> -5

The final line, ~(a ^ mask), is the standard way to reinterpret a 32-bit pattern as a negative Python integer. The same mask-first mindset applies to Reverse Bits, where the loop must run exactly 32 times: 43261596 reversed to 964176192 in the test.

When bits are the wrong tool

  • Readability matters more than saving a few operations. A set expresses intent better than a mask unless the problem asks for constant extra space.
  • The numbers are large or unbounded, so the 2n mask loop explodes.
  • The bit trick hides a requirement. Single Number only works because each other value appears an exact number of times.

If you are choosing what to study first, the coding interview roadmap places bit tricks after arrays and hashing, and the Python cheat sheet lists the built-ins worth knowing. Complexity for every trick above is O(n) time and O(1) extra space, except subsets and counting bits, which are O(n · 2n) and O(n) respectively.

Keep learning