Bit Tricks: XOR, Power of Two and Counting Set Bits
20 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Three small bit tricks turn up again and again in coding rounds: XOR to cancel pairs, n & (n - 1) to drop the lowest 1 bit, and bit counting. Each one replaces a loop or an extra list with a single expression, and each has a plain-words reason why it works.
XOR cancels equal numbers
The XOR cancel rule says x ^ x is 0 and x ^ 0 is x, in any order. XOR of a list therefore keeps only values that appear an odd number of times.
XOR of a number with itself is 0, and XOR with 0 changes nothing. The order does not matter. So XOR-ing a whole list wipes out every pair and leaves what has no partner.
print(5 ^ 5, 5 ^ 0, 3 ^ 5 ^ 3)The 3s cancel, so 3 ^ 5 ^ 3 is just 5, even though the 5 sits between them.
Single number: find the value without a partner
Every order id was logged twice except one. A Counter or a sorted list finds it, but XOR does it in one pass with no extra memory.
from functools import reducefrom operator import xor
ids = [4, 9, 4, 7, 9]print(reduce(xor, ids))Example 1 · Single number: brute force, counter, XOR
from collections import Counter
ids = [4, 9, 4, 7, 9]print([x for x in ids if ids.count(x) == 1][0])print(next(k for k, c in Counter(ids).items() if c == 1))x = 0for v in ids: x ^= vprint(x)7 7 7
What this code does
ids.countrescans the list for every id, so the first line takes O(n squared) time.- Counter makes it O(n) time but O(n) space. The XOR loop is O(n) time and O(1) space.
Example 2 · Missing number from 0 to n
nums = [3, 0, 1]x = len(nums)for i, v in enumerate(nums): x ^= i ^ vprint(x)2
What this code does
- The list should hold 0 to n but one value is gone. XOR every index and every value together with n.
- Each present number appears twice and cancels, so the missing 2 is what remains.
reduce(xor, ids) folds the list with ^. The 4s and 9s cancel, so 7 is left. That is O(n) time and O(1) space.
Power of two in one line
The lowest set bit trick is that n & (n - 1) clears the lowest 1 bit of n. If the result is 0, n had only one 1 bit, so it is a power of two.
A power of two has exactly one 1 bit. Subtracting 1 turns that bit off and every bit below it on, so the two numbers share no bits.
def is_power_of_two(n): return n > 0 and (n & (n - 1)) == 0
print([is_power_of_two(n) for n in (1, 6, 8, 0, 64)])Example 3 · Swap and lowest set bit
a, b = 3, 5a ^= bb ^= aa ^= bprint(a, b)print(12 & -12)5 3 4
What this code does
- Three XORs swap two numbers without a third variable. This is a classic question.
- In real Python write
a, b = b, a. The last line showsn & -n, which keeps only the lowest set bit: 12 is 1100, so the answer is 4.
The n > 0 test matters: 0 & -1 is 0, so without it 0 would pass.
Counting set bits
A set bit is a bit whose value is 1. Counting set bits is also called the population count, or popcount, of a number.
Interviews ask how many 1 bits a number has. Python 3.10 added int.bit_count. The older way counts the 1s in the binary text.
n = 0b101101print(n.bit_count())print(bin(n).count("1"))Example 4 · Counting bits by hand (Kernighan)
def count_ones(n): count = 0 while n: n &= n - 1 count += 1 return count
print(count_ones(0b101101), count_ones(255), count_ones(0))4 8 0
What this code does
- Each
n &= n - 1removes the lowest 1 bit, so the loop runs once per set bit, not once per bit position. - It prints 4, 8 and 0, the same as
bit_count.
Example 5 · Bit counts for a range, and bit_length
print([i.bit_count() for i in range(8)])bits = [0] * 8for i in range(1, 8): bits[i] = bits[i >> 1] + (i & 1)print(bits)print((37).bit_length())[0, 1, 1, 2, 1, 2, 2, 3] [0, 1, 1, 2, 1, 2, 2, 3] 6
What this code does
i >> 1is i without its last bit, and its count is already known, so one addition builds each answer.bit_lengthis the number of bits needed: 37 is 100101, six bits.
Both print 4. Use bit_count in real code. Interviewers often also want the hand-written loop, shown in the examples.
Next step
Check your understanding
10 quick questions