Bit Manipulation in Python
Bit manipulation means working directly with the binary (base-2) representation of numbers using bitwise operators. Many problems become faster, cleaner, and more elegant when solved using bits—especially in competitive programming and interviews.
Bit manipulation is heavily used in:
- Optimization problems
- Subset and mask-based problems
- XOR-based tricks
- Low-level performance tuning
Computers store integers as binary numbers (0s and 1s).
Bitwise operators act directly on these bits.
AND (&)
Returns 1 only if both bits are 1.
print(5 & 3) # 0101 & 0011 = 0001 => 1
OR (|)
Returns 1 if at least one bit is 1.
print(5 | 3) # 0101 | 0011 = 0111 => 7
XOR (^)
Returns 1 if bits are different.
print(5 ^ 3) # 0101 ^ 0011 = 0110 => 6
NOT (~)
Flips all bits.
In Python, this results in a negative number due to infinite-bit representation.
print(~5) # -6
Left Shift (<<)
Shifts bits left (multiplies by 2 for each shift).
print(5 << 1) # 10
print(5 << 2) # 20
Right Shift (>>)
Shifts bits right (integer division by 2 for each shift).
print(5 >> 1) # 2
print(20 >> 2) # 5
Checking if a Number is Odd or Even
Logic
- Odd numbers → last bit is
1 - Even numbers → last bit is
0
def is_odd(n):
return (n & 1) == 1
print(is_odd(7)) # True
print(is_odd(10)) # False
Complexity: O(1)
Finding the i-th Bit of a Number
Logic
- Create a mask:
1 << i - AND with the number
def get_ith_bit(n, i):
return (n & (1 << i)) != 0
print(get_ith_bit(13, 2)) # True (13 = 1101)
print(get_ith_bit(13, 1)) # False
Setting the i-th Bit (Make it 1)
Logic
- OR with a mask
def set_ith_bit(n, i):
return n | (1 << i)
print(set_ith_bit(9, 1)) # 9=1001 → 1011 => 11
Clearing the i-th Bit (Make it 0)
Logic
- AND with inverted mask
def clear_ith_bit(n, i):
return n & ~(1 << i)
print(clear_ith_bit(13, 2)) # 1101 → 1001 => 9
Toggling the i-th Bit (Flip it)
Logic
- XOR with mask
def toggle_ith_bit(n, i):
return n ^ (1 << i)
print(toggle_ith_bit(13, 1)) # 1101 → 1111 => 15
Method 1: Python Built-in
def count_ones(n):
return bin(n).count("1")
print(count_ones(13)) # 3
Method 2: Brian Kernighan’s Algorithm (Efficient)
Removes the lowest set bit in each iteration.
def count_ones_kernighan(n):
count = 0
while n:
n = n & (n - 1)
count += 1
return count
print(count_ones_kernighan(13)) # 3
Complexity: O(number of set bits)
Very fast when few bits are set.
Check if a Number Is a Power of Two
A power of two has exactly one set bit.
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
Find the Only Non-Repeating Number (XOR Trick)
If every number appears twice except one, XOR reveals the unique number.
def single_number(nums):
x = 0
for n in nums:
x ^= n
return x
print(single_number([2, 2, 1, 4, 4])) # 1
Why it works
a ^ a = 00 ^ b = b
- Optimization: reduce memory using bitmasks
- Subset generation: represent subsets using bits
- Fast checks: odd/even, power of two, parity
- XOR-based problems: unique number, missing number
- Competitive programming: bitmask DP, state compression
Example: Generating All Subsets Using Bitmask
Each subset corresponds to a binary number from 0 to 2ⁿ - 1.
def subsets(nums):
n = len(nums)
result = []
for mask in range(1 << n):
subset = []
for i in range(n):
if mask & (1 << i):
subset.append(nums[i])
result.append(subset)
return result
print(subsets([1, 2, 3]))
Complexity: O(n · 2ⁿ)
Bit manipulation allows you to write fast, memory-efficient, and elegant solutions by working directly with binary representations. Master the operators & | ^ ~ << >> and common tricks like:
- odd/even checks
- extracting, setting, clearing bits
- counting set bits
- XOR-based uniqueness problems