DSA · Chapter 39 of 40
Bit Manipulation
Bitwise operators work directly on the binary representation of integers: AND, OR, XOR, NOT and shifts. They give O(1) tricks for problems about parity, subsets and unique elements.
XOR is the star: x ^ x = 0 and x ^ 0 = x, so XOR-ing every element of an array cancels the pairs and leaves the single element.
Common tricks
n & 1 tests odd, n >> 1 halves, n & (n - 1) clears the lowest set bit, and n & (n - 1) == 0 tests a power of two.
Bitmasks
An integer can represent a subset of up to 32 items, which is used in bitmask DP and travelling-salesman style problems.
Example 1 (python)
nums = [4, 1, 2, 1, 2]
res = 0
for n in nums:
res ^= n
print(res)Output
4XOR cancels the duplicated pairs.
Example 2 (python)
def count_bits(n):
c = 0
while n:
n &= n - 1
c += 1
return c
print(count_bits(13))Output
3n & (n-1) clears one set bit per iteration (13 = 1101).
Key points
- x ^ x = 0 and x ^ 0 = x.
- n & (n - 1) clears the lowest set bit.
- n & (n - 1) == 0 checks for a power of two.
- Bitmasks encode subsets compactly.
💡 Note: Watch out for negative numbers and language-specific shift behaviour.