Bit Manipulation: The Tricks That Keep Appearing in Interviews

Quick Answer

Learn AND, OR, XOR, NOT and the two shifts. Then four patterns: n&1 tests odd, n&(n-1) clears the lowest set bit, XOR of a value with itself is zero, and shifting multiplies or divides by two.

The operators

All of them work bit by bit on the binary representation.

• & AND — 1 only if both bits are 1.
• | OR — 1 if either is 1.
• ^ XOR — 1 if the bits differ.
• ~ NOT — flips every bit.
• << and >> — shift left or right.

n = 12
print(bin(n))       # 0b1100
print(n << 1)       # 24   -- doubles
print(n >> 1)       # 6    -- halves

Shifting left by one appends a zero, which doubles the value. Shifting right discards the lowest bit, halving and rounding down. That is why x >> 1 appears in binary search implementations instead of x // 2.

Testing odd or even

print(n & 1 == 0)   # True -- 12 is even

The lowest bit is 1 exactly when the number is odd, because it represents the ones place. So n & 1 extracts it.

This is not faster than n % 2 in any language you are likely to use — modern compilers produce identical code. It matters because you will read it in other people's code, and because it makes the follow-up questions easier to see.

n & (n-1): the most useful trick

Subtracting 1 from a number flips its lowest set bit to 0 and turns every bit below it to 1. ANDing with the original therefore clears the lowest set bit.

That gives two classic results immediately.

Power of two check. A power of two has exactly one set bit, so clearing it gives zero:

print(12 & (12 - 1) == 0)   # False
print(16 & (16 - 1) == 0)   # True

Counting set bits. Repeat the operation until the number is zero, and the number of iterations is the number of set bits — which loops once per set bit rather than once per bit:

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

print(bin(12).count('1'))   # 2, the readable way

In Python, bin(n).count('1') is clearer and perfectly acceptable. Know the bit version because it is what gets asked.

XOR: the single number problem

XOR has three properties that combine into something useful: x ^ x == 0, x ^ 0 == x, and it is commutative, so order does not matter.

So in a list where every value appears twice except one, XORing everything cancels the pairs and leaves the odd one out:

nums = [4, 1, 2, 1, 2]
x = 0
for v in nums:
    x ^= v
print(x)   # 4

One pass, no extra memory. The alternative with a hash set uses O(n) space; this uses O(1).

The related trick, swapping without a temporary:

a, b = 5, 9
a ^= b; b ^= a; a ^= b
print(a, b)   # 9 5

Worth knowing, and worth not using — a, b = b, a is clearer, and the XOR version breaks if both names refer to the same variable.

Where this appears outside interviews

Bit manipulation is not only puzzle material.

• Flags in a single integer. Permissions are the classic case — read is 4, write is 2, execute is 1, so chmod 755 is three sets of bit flags. Checking is flags & WRITE, setting is flags |= WRITE, clearing is flags &= ~WRITE.
• Bitmasks in dynamic programming — representing a subset of up to about 20 items as one integer, which is how travelling-salesman style DP is done.
• Hashing and checksums rely heavily on XOR and shifts.
• Network masks — subnetting is AND applied to IP addresses.

A caution specific to Python: integers are arbitrary precision and negative numbers behave as if they have infinitely many leading ones, so ~5 is -6 rather than a fixed-width flip. Tricks copied from C that assume 32-bit wrapping need a mask such as & 0xFFFFFFFF to behave the same way.

Frequently Asked Questions