Bit Manipulation: Tricks and 6 Practice Problems

The previous post laid out the operators. This one is where they become weapons. We start with five tricks worth memorising, then apply them to six classic problems.

Trick 1 — n & (n - 1) clears the lowest set bit

Subtracting one from n flips every trailing zero to one and turns the lowest set bit into zero. ANDing with n then clears that bit and everything below it — which is now all zeros anyway.

n     = 0b 1 0 1 1 0 0
n - 1 = 0b 1 0 1 0 1 1
─────────────────────────  AND
n&(n-1)= 0b 1 0 1 0 0 0
▲
this 1 is now 0; the trailing 00 below was already 0

n = 0b101100
print(bin(n & (n - 1)))    # 0b101000

This trick is the basis of Brian Kernighan’s bit count — you can count set bits by repeatedly clearing the lowest one.

Trick 2 — n & -n isolates the lowest set bit

In two’s complement, -n is ~n + 1. ANDing n with -n keeps exactly the lowest bit that is set in n.

n = 0b101100
print(bin(n & -n))    # 0b100

Useful when you need to know where the lowest set bit is without clearing it. Fenwick trees (binary indexed trees) live on this trick.

Trick 3 — x ^ x = 0 and x ^ 0 = x

XOR cancels duplicates and preserves singletons. Apply it across a list and every pair cancels — what is left is the unique element.

print(5 ^ 5)        # 0
print(5 ^ 0)        # 5
print(5 ^ 3 ^ 5)    # 3

XOR is also commutative and associative — order doesn’t matter. That is what makes Single Number (problem 1 below) so satisfying.

Trick 4 — swap two numbers without a temp

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

A classic curiosity. In Python you would just write a, b = b, a, but seeing why it works deepens your XOR intuition.

Trick 5 — count set bits with Brian Kernighan’s method

The naive bit count loops over every bit, even the zeros:

def count_naive(n):
    c = 0
    while n:
        c += n & 1
        n >>= 1
    return c

Brian Kernighan’s method loops only as many times as there are set bits:

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

print(count_bits(0b10110101))    # 5

step 0: n = 1 0 1 1 0 1 0 1     count = 0
step 1: n &= n-1                count = 1
n = 1 0 1 1 0 1 0 0
step 2: n &= n-1                count = 2
n = 1 0 1 1 0 0 0 0
step 3: n &= n-1                count = 3
n = 1 0 1 0 0 0 0 0
step 4: n &= n-1                count = 4
n = 1 0 0 0 0 0 0 0
step 5: n &= n-1                count = 5
n = 0 0 0 0 0 0 0 0  → loop ends

Five iterations for five set bits. The naive version takes eight (the position of the highest set bit + 1).

Practice problems

1. Single Number

Problem. Every element in nums appears twice except one. Find the one that appears once. Linear time, constant space.

Examples. [2, 2, 1] → 1. [4, 1, 2, 1, 2] → 4.

Insight. XOR all elements together. Pairs cancel; the unique element survives.

0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4    ◀── the unique element

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

print(single_number([4, 1, 2, 1, 2]))    # 4

One pass, O(1) extra space. The order of nums does not matter — XOR is commutative.

2. Number of 1 Bits (Hamming Weight)

Problem. Count the 1 bits in the binary representation of an unsigned integer.

Examples. 11 = 0b1011 → 3. 128 = 0b10000000 → 1.

Solution — Brian Kernighan:

def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

print(hamming_weight(11))     # 3
print(hamming_weight(128))    # 1

Python also has n.bit_count() (3.10+) for the one-liner. But knowing the manual version is the point.

3. Power of Two

Problem. Given an integer n, return True if it is a positive power of two.

Examples. 1, 2, 4, 8, 16 → True. 0, 3, 5, 6 → False.

Insight. A power of two has exactly one set bit. So n & (n - 1) == 0 (assuming n > 0).

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

print(is_power_of_two(16))    # True
print(is_power_of_two(18))    # False

For n = 16 = 0b10000, n - 1 = 0b01111, and the AND is 0. For n = 18 = 0b10010, the AND is 0b10000 — not zero.

4. Counting Bits

Problem. Given n, return a list ans of length n + 1 where ans[i] is the number of 1 bits in i.

Examples. n = 5 → [0, 1, 1, 2, 1, 2].

Naive. Apply hamming_weight to every i. O(n log n).

DP insight. bits(i) = bits(i >> 1) + (i & 1). The number of bits in i is the number of bits in i // 2 plus the parity of i.

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

print(count_bits_list(5))    # [0, 1, 1, 2, 1, 2]

Or, using Brian Kernighan’s trick: ans[i] = ans[i & (i - 1)] + 1 — each value’s bit count is one more than the value with its lowest bit cleared.

def count_bits_list(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i & (i - 1)] + 1
    return ans

Both are O(n).

5. Missing Number

Problem. Given a list of n distinct integers from the range [0, n], find the one missing.

Examples. [3, 0, 1] → 2. [0, 1] → 2. [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8.

XOR insight. XOR every index 0..n together, then XOR every value in nums. Pairs cancel; the missing value is what is left.

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

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

Why start result = len(nums)? Because the indices we use are 0..len(nums)-1, but the full range is 0..len(nums). Starting at len(nums) puts that last index into the XOR.

This works in O(n) time and O(1) space — better than sorting (O(n log n)) and just as fast as the sum trick, with no overflow concern.

6. Reverse Bits

Problem. Reverse the bits of a 32-bit unsigned integer.

Examples. 0b00000010100101000001111010011100 → 0b00111001011110000010100101000000.

Approach. Build the result one bit at a time. For each of 32 iterations, shift result left, take the lowest bit of n, and OR it in. Then shift n right.

def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

print(bin(reverse_bits(0b00000010100101000001111010011100)))
# 0b111001011110000010100101000000

The leading zeros disappear in bin() output, but the underlying integer is the right 32-bit value.

A small extra — XOR find two unique numbers

If every element appears twice except two, you can still solve it in O(n) time and O(1) space. XOR everything together — the result is a ^ b. Then use n & -n to find one bit where a and b differ, partition the list by that bit, and XOR each partition separately.

def two_unique(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n
    diff_bit = xor_all & -xor_all
    a = b = 0
    for n in nums:
        if n & diff_bit:
            a ^= n
        else:
            b ^= n
    return a, b

print(two_unique([1, 2, 1, 3, 2, 5]))    # (3, 5) or (5, 3)

This is a small masterpiece — two unrelated tricks (XOR cancellation + n & -n) combining into a clean algorithm.

Recap

You now have:

• n & (n - 1) — clears the lowest set bit
• n & -n — isolates the lowest set bit
• x ^ x = 0, x ^ 0 = x — XOR cancels duplicates
• Brian Kernighan’s bit count — loops once per set bit
• Six worked classic problems with linear-time bitwise solutions

Next steps

You now have the recursion, DP, and bit manipulation building blocks. From here, the natural next step is graphs and trees — where BFS, DFS, and shortest-path algorithms put recursion and DP to work on more complex structures.

Questions or feedback? Email codeloomdevv@gmail.com.