Bit Manipulation
DSA · Algorithm Techniques
Theory
Bit manipulation works directly on the binary representation of integers using AND (&), OR (|), XOR (^), NOT (~) and shifts (<< and >>). Useful facts: x & 1 tells whether x is odd, x & (x-1) clears the lowest set bit, a ^ a = 0 and a ^ 0 = a. A bitmask can represent a set of up to 64 items in one integer.
Why we use it
Bit tricks are extremely fast, use little memory and solve some problems elegantly.
When to use it
Use them for flags and permissions, finding the single unique number, counting set bits, subsets via bitmasks, and checking powers of two.
How it works
- Number in binary
- Check bit i? Yes: (x >> i) & 1. No: Set: x | (1 << i); clear: x & ~(1 << i).
- x & (x - 1) clears the lowest set bit
- Operations run in O(1)
Syntax
x & 1 odd check
x & (x - 1) clear lowest set bit
x & (x - 1) == 0 power of two (x > 0)
1 << k k-th bit mask
a ^ b ^ a = b XOR cancels pairsExample
def count_bits(x):
c = 0
while x:
x &= x - 1
c += 1
return c
def single_number(nums):
r = 0
for n in nums:
r ^= n
return r
READ, WRITE, ADMIN = 1, 2, 4
user = READ | WRITE
print("13 in binary:", bin(13), "| set bits:", count_bits(13))
print("Is 64 a power of two:", 64 & 63 == 0)
print("Single number in [4,1,2,1,2]:", single_number([4, 1, 2, 1, 2]))
print("User can write:", bool(user & WRITE), "| admin:", bool(user & ADMIN))Key points
- AND, OR, XOR, NOT and shifts
- x & (x-1) removes the lowest set bit
- XOR cancels equal pairs
- Bitmasks store small sets compactly