Bit Manipulation: The Tricks That Make Interviewers Think You're a Genius

Bit manipulation has a reputation for being mysterious. People see expressions like n & (n - 1) and assume it's some arcane magic that only systems programmers need to know. In reality, there are maybe a dozen tricks worth knowing, they all follow from basic properties of binary arithmetic, and they show up in interviews more often than you'd expect.

Let's demystify the whole thing.

Binary Basics You Need

A quick refresher. In binary, each position represents a power of 2:

13 in binary: 1101
             = 18 + 14 + 02 + 11
             = 8 + 4 + 1 = 13

The six bitwise operators:

Operator	Symbol	What it does
AND	a & b	1 only if both bits are 1
OR	a \	b	1 if either bit is 1
XOR	a ^ b	1 if bits are different
NOT	~a	Flip all bits
Left shift	a << k	Shift bits left by k (multiply by 2^k)
Right shift	a >> k	Shift bits right by k (divide by 2^k)

If you understand these six, everything else is just combinations of them.

The Essential Tricks

Check if a Number is Even or Odd

The least significant bit tells you. If it's 1, the number is odd. If it's 0, even.

def is_odd(n):
    return n & 1 == 1

def is_even(n):
    return n & 1 == 0

This is faster than n % 2 in many languages (though modern compilers optimize % 2 to a bit operation anyway). More importantly, it shows you understand bits.

Check if a Number is a Power of Two

A power of two in binary has exactly one bit set: 1, 10, 100, 1000, etc. The number minus one has all the lower bits set: 0, 01, 011, 0111.

AND them together: zero. Always.

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

The n & (n - 1) trick clears the lowest set bit. If the result is 0, there was only one set bit — power of two.

Count Set Bits (Hamming Weight)

How many 1s are in the binary representation?

def count_bits(n):
    count = 0
    while n:
        n &= (n - 1)  # clear lowest set bit
        count += 1
    return count

Each iteration clears one set bit. The loop runs exactly k times where k is the number of set bits. Much better than checking all 32 (or 64) bit positions.

Python also has bin(n).count('1'), but the bit trick is what interviewers want to see.

Get, Set, Clear, and Toggle a Specific Bit

These are the fundamental bit manipulation primitives. Every other trick builds on them.

def get_bit(n, i):
    """Check if bit at position i is set (0-indexed from right)"""
    return (n >> i) & 1

def set_bit(n, i):
    """Set bit at position i to 1"""
    return n | (1 << i)

def clear_bit(n, i):
    """Set bit at position i to 0"""
    return n & ~(1 << i)

def toggle_bit(n, i):
    """Flip bit at position i"""
    return n ^ (1 << i)

The pattern: create a mask with 1 << i (a single 1 at position i), then apply the appropriate operator.

XOR — The Swiss Army Knife

XOR has three properties that make it incredibly useful:

1. a ^ a = 0 (anything XOR itself is 0)
2. a ^ 0 = a (anything XOR 0 is itself)
3. XOR is commutative and associative (order doesn't matter)

These properties lead to some elegant solutions. Find the single number: Given an array where every element appears twice except one, find the unique one.

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

Every pair XORs to 0. The unique number XORs with 0 and survives. O(n) time, O(1) space. No hash maps needed.

Swap two numbers without a temporary variable:

def swap(a, b):
    a ^= b
    b ^= a
    a ^= b
    return a, b

Cute trick. Don't use it in production code — it's less readable than a normal swap and fails when a and b reference the same memory. But interviewers love it.

Find Two Single Numbers

What if there are two unique numbers (everything else appears twice)? XOR all elements — you get a ^ b. Since a != b, at least one bit in the result is set. Use that bit to divide all numbers into two groups. Each group contains exactly one unique number.

def single_number_iii(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n

# find any set bit (rightmost set bit)
    diff_bit = xor_all & (-xor_all)

a, b = 0, 0
    for n in nums:
        if n & diff_bit:
            a ^= n
        else:
            b ^= n

return [a, b]

The n & (-n) trick isolates the rightmost set bit. In two's complement, -n flips all bits and adds 1, which means the rightmost set bit is the only bit that's 1 in both n and -n.

Using Bits as Sets

An integer can represent a set of elements (up to 32 or 64). Bit i is set means element i is in the set.

# set operations using bits
union = a | b
intersection = a & b
difference = a & ~b
symmetric_diff = a ^ b
is_subset = (a & b) == a
add_element = s | (1 << i)
remove_element = s & ~(1 << i)
has_element = (s >> i) & 1

This is incredibly useful for problems involving subsets. Iterating over all subsets of n elements:

# iterate all subsets of {0, 1, ..., n-1}
for mask in range(1 << n):
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(i)
    # process subset

2^n subsets, each generated in O(n) time. This is the backbone of bitmask DP.

Iterate Over Set Bits

Instead of checking all n positions, iterate only over the bits that are actually set:

def iterate_set_bits(mask):
    while mask:
        lowest_bit = mask & (-mask)   # isolate lowest set bit
        bit_position = lowest_bit.bit_length() - 1
        # process bit_position
        mask &= mask - 1  # clear lowest set bit

This runs in O(k) where k is the number of set bits, not O(n) where n is the total number of bit positions.

Iterate Over All Submasks of a Mask

Given a bitmask, iterate over all of its submasks (including itself and 0):

def iterate_submasks(mask):
    submask = mask
    while submask > 0:
        # process submask
        submask = (submask - 1) & mask
    # don't forget to process submask = 0 if needed

This clever trick generates all submasks in descending order. The total work across all masks and their submasks is O(3^n) — each bit is either "in the outer mask and in the submask," "in the outer mask but not the submask," or "not in the outer mask." Three choices per bit.

Bitmask Dynamic Programming

Bitmask DP uses integers to represent states where you've made choices about a set of elements. Classic example: the Traveling Salesman Problem.

def tsp(dist, n):
    # dp[mask][i] = min cost to visit all cities in mask, ending at city i
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0

for mask in range(1 << n):
        for last in range(n):
            if dp[mask][last] == INF:
                continue
            if not (mask & (1 << last)):
                continue
            for next_city in range(n):
                if mask & (1 << next_city):
                    continue  # already visited
                new_mask = mask | (1 << next_city)
                dp[new_mask][next_city] = min(
                    dp[new_mask][next_city],
                    dp[mask][last] + dist[last][next_city]
                )

full_mask = (1 << n) - 1
    return min(dp[full_mask][i] + dist[i][0] for i in range(n))

O(2^n n^2) time, O(2^n n) space. Exponential, but much better than the naive O(n!) brute force. Bitmask DP is practical for n up to about 20.

Other Useful Tricks

Compute absolute value without branching:

def abs_value(n):
    mask = n >> 31  # all 1s if negative, all 0s if positive (32-bit)
    return (n + mask) ^ mask

Round up to the next power of two:

def next_power_of_two(n):
    n -= 1
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    return n + 1

This fills in all the bits below the highest set bit, then adds 1.

Check if two integers have opposite signs:

def opposite_signs(a, b):
    return (a ^ b) < 0

The sign bit of a ^ b is 1 only if the sign bits of a and b differ.

Common Mistakes

Operator precedence. Bitwise operators have surprisingly low precedence in most languages. x & 1 == 0 is parsed as x & (1 == 0), not (x & 1) == 0. Always use parentheses. Signed vs. unsigned right shift. In languages like Java, >> is arithmetic (preserves sign bit) and >>> is logical (fills with zeros). Python doesn't have unsigned types, so this is less of an issue, but be careful in Java and C++. Assuming 32-bit integers. Python integers are arbitrary precision. If you're porting a bit trick from C++ to Python, operations like ~n might give unexpected results because Python doesn't truncate to 32 bits. Use n & 0xFFFFFFFF to simulate 32-bit behavior. Off-by-one in bit positions. Bits are 0-indexed from the right. The rightmost bit is position 0, not position 1. 1 << 0 is 1 (the rightmost bit), 1 << 1 is 2 (second from right).

When to Reach for Bit Manipulation

Bit manipulation isn't the answer to everything. Use it when:

• The problem explicitly involves binary representations or powers of 2
• You need O(1) space where a hash set would normally be used (like single number problems)
• You're working with subsets and the number of elements is small (n <= 20)
• The problem involves toggling states, tracking presence/absence, or computing parity
• You need bitmask DP for an NP-hard problem with small input

Don't force it. If a hash map solution is clean and efficient, using bit manipulation just to be clever is not an improvement. But when the problem is naturally about bits — recognizing that early saves you a lot of effort.

Practice these patterns on CodeUp. Start with the basic tricks (single number, power of two, counting bits), then work up to bitmask DP problems. The tricks themselves are simple — the skill is recognizing which problems they apply to.