AdvancedBit Manipulation & Math
Three bit tricks worth knowing
x ^ x = 0 finds the odd one out, n & (n − 1) drops the lowest 1-bit, and (n >> i) & 1 reads bit i.
The idea
XOR cancels equal values: a ^ a = 0 and a ^ 0 = a, in any order. XOR everything together and pairs vanish, leaving the single number.
n & (n − 1) clears the lowest set bit, so counting how many times you can do it counts the 1-bits; it's 0 only for powers of two (n > 0).
Worked example
Single Number on [4, 1, 2, 1, 2]
- 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4
In code (Python)
def single_number(nums):
result = 0
for x in nums:
result ^= x
return result
def count_ones(n):
count = 0
while n:
n &= n - 1 # drop the lowest 1-bit
count += 1
return count
def is_power_of_two(n):
return n > 0 and n & (n - 1) == 0O(n) for single number; O(number of 1-bits) for counting.
How to spot it
- “appears once, others twice”, counting bits, powers of two, toggling flags.
Common mistakes
- Python ints don't overflow, so problems that assume 32-bit need masking (& 0xFFFFFFFF).
- Operator precedence: write n & (n - 1) == 0 with care in other languages.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →