Solution: Essential Bit Manipulation Techniques
# 1. Check if Power of 2
def isPowerOfTwo(n):
"""
Power of 2 has exactly one bit set
n = 8 = 1000, n-1 = 7 = 0111
n & (n-1) = 0000 = 0
Time: O(1), Space: O(1)
"""
return n > 0 and (n & (n - 1)) == 0
print(isPowerOfTwo(16)) # True
print(isPowerOfTwo(6)) # False
# 2. Count Set Bits (Brian Kernighan's Algorithm)
def countSetBits(n):
"""
Each iteration removes rightmost set bit
n = 13 = 1101
n & (n-1) = 1100 (removed rightmost 1)
n & (n-1) = 1000 (removed another 1)
...
Time: O(number of set bits), Space: O(1)
"""
count = 0
while n:
n &= (n - 1) # Remove rightmost set bit
count += 1
return count
print(countSetBits(13)) # 3 (binary: 1101)
# 3. Single Number (XOR trick)
def singleNumber(nums):
"""
LeetCode 136: Find number that appears once
All others appear twice
XOR properties:
- a ^ a = 0
- a ^ 0 = a
- XOR is commutative and associative
[2,2,1] -> 2^2^1 = 0^1 = 1
Time: O(n), Space: O(1)
"""
result = 0
for num in nums:
result ^= num
return result
print(singleNumber([4,1,2,1,2])) # 4
# 4. Get/Set/Clear/Toggle Bit
def bitOperations(n, i):
"""Operations on ith bit (0-indexed from right)"""
# Get ith bit
get_bit = (n >> i) & 1
# Set ith bit to 1
set_bit = n | (1 << i)
# Clear ith bit to 0
clear_bit = n & ~(1 << i)
# Toggle ith bit
toggle_bit = n ^ (1 << i)
return {
'original': bin(n),
'get_bit': get_bit,
'set_bit': bin(set_bit),
'clear_bit': bin(clear_bit),
'toggle_bit': bin(toggle_bit)
}
print(bitOperations(10, 1)) # n=1010, i=1 (second bit from right)
# 5. Add Two Numbers Without + Operator
def getSum(a, b):
"""
LeetCode 371: Sum without + operator
Use XOR for sum without carry
Use AND << 1 for carry
Example: 5 + 3
5 = 0101, 3 = 0011
sum = 5 ^ 3 = 0110 = 6
carry = (5 & 3) << 1 = 0010 = 2
Repeat: 6 + 2
sum = 6 ^ 2 = 0100 = 4
carry = (6 & 2) << 1 = 1000 = 8
Repeat: 4 + 8 = 12... until carry is 0
Time: O(1) for 32-bit integers, Space: O(1)
"""
# Mask to handle negative numbers in Python
mask = 0xFFFFFFFF
while b != 0:
# Calculate sum without carry
sum_without_carry = (a ^ b) & mask
# Calculate carry
carry = ((a & b) << 1) & mask
a = sum_without_carry
b = carry
# Handle negative numbers
return a if a <= 0x7FFFFFFF else ~(a ^ mask)
print(getSum(5, 3)) # 8
# 6. Reverse Bits
def reverseBits(n):
"""
LeetCode 190: Reverse bits of 32-bit integer
Time: O(1), Space: O(1)
"""
result = 0
for i in range(32):
# Get ith bit from right of n
bit = (n >> i) & 1
# Set it at (31-i)th position from right in result
result |= (bit << (31 - i))
return result
print(bin(reverseBits(0b00000010100101000001111010011100)))
# 7. Missing Number using XOR
def missingNumber(nums):
"""
LeetCode 268: Find missing number in [0, n]
XOR all numbers and all indices
Duplicates cancel out, missing remains
[3,0,1] -> indices [0,1,2,3]
0^1^2^3^3^0^1 = 2
Time: O(n), Space: O(1)
"""
n = len(nums)
result = n
for i, num in enumerate(nums):
result ^= i ^ num
return result
print(missingNumber([3,0,1])) # 2
# 8. Count Bits from 0 to n
def countBits(n):
"""
LeetCode 338: Count bits for every number from 0 to n
Optimization: bits[i] = bits[i >> 1] + (i & 1)
Remove rightmost bit and add back current bit
Time: O(n), Space: O(n)
"""
result = [0] * (n + 1)
for i in range(1, n + 1):
result[i] = result[i >> 1] + (i & 1)
return result
print(countBits(5)) # [0,1,1,2,1,2]
# 9. Bitwise AND of Range
def rangeBitwiseAnd(left, right):
"""
LeetCode 201: Bitwise AND of all numbers in [left, right]
Find common prefix of left and right in binary
Example: [5,7] -> 101, 110, 111
AND = 100 (common prefix)
Time: O(log n), Space: O(1)
"""
shift = 0
# Find common prefix
while left < right:
left >>= 1
right >>= 1
shift += 1
return left << shift
print(rangeBitwiseAnd(5, 7)) # 4 (binary: 100)
# 10. Swap Two Numbers Without Temp Variable
def swap(a, b):
"""Using XOR to swap"""
print(f"Before: a={a}, b={b}")
a = a ^ b
b = a ^ b # b = (a^b)^b = a
a = a ^ b # a = (a^b)^a = b
print(f"After: a={a}, b={b}")
return a, b
swap(5, 10)
Advanced: Subset Generation Using Bits
def subsets(nums):
"""
Generate all subsets using bit manipulation
For [1,2,3], there are 2^3 = 8 subsets
Represent each subset as binary number:
000 -> []
001 -> [3]
010 -> [2]
011 -> [2,3]
100 -> [1]
...
Time: O(n * 2^n), Space: O(1) excluding output
"""
n = len(nums)
result = []
# Iterate through all possible subsets (2^n)
for mask in range(1 << n): # 2^n
subset = []
for i in range(n):
# Check if ith bit is set
if mask & (1 << i):
subset.append(nums[i])
result.append(subset)
return result
print(subsets([1,2,3]))
Complexity Analysis
Time Complexity:
- Most bit operations: O(1)
- Counting bits: O(log n) or O(number of set bits)
- Subset generation: O(n * 2^n)
Space Complexity:
- Usually O(1) - only using bitwise operations
- No extra data structures needed
Key Takeaways
- Bit manipulation provides O(1) solutions for many problems
- XOR is powerful for finding unique elements
n & (n-1) removes rightmost set bit- Shifting is faster than multiplication/division by powers of 2
- Understand two's complement for negative numbers
Related Problems
