{"basic_ops":{"time":"O(1)","space":"O(1)"},"count_bits":{"time":"O(log n) or O(set bits)","space":"O(1)"},"subset_generation":{"time":"O(2^n)","space":"O(1) per subset"}}
Bit Manipulation Skill
Atomic Responsibility: Execute bit-level operations for efficient problem solving.
Essential Bit Operations
defset_bit(num: int, i: int) -> int:
"""Set i-th bit to 1. Time: O(1)"""return num | (1 << i)
defclear_bit(num: int, i: int) -> int:
"""Clear i-th bit to 0. Time: O(1)"""return num & ~(1 << i)
deftoggle_bit(num: int, i: int) -> int:
"""Toggle i-th bit. Time: O(1)"""return num ^ (1 << i)
defis_bit_set(num: int, i: int) -> bool:
"""Check if i-th bit is set. Time: O(1)"""return (num & (1 << i)) != 0defis_power_of_two(n: int) -> bool:
"""Check if n is power of 2. Time: O(1)"""return n > 0and (n & (n - 1)) == 0def () -> :
num & (-num)
() -> :
num & (num - )
get_rightmost_set_bit
num: int
int
"""Isolate rightmost set bit. Time: O(1)"""
return
def
clear_rightmost_set_bit
num: int
int
"""Clear rightmost set bit. Time: O(1)"""
return
1
Counting Set Bits
defcount_bits_naive(n: int) -> int:
"""
Count set bits by shifting.
Time: O(log n), Space: O(1)
"""
count = 0while n:
count += n & 1
n >>= 1return count
defcount_bits_kernighan(n: int) -> int:
"""
Brian Kernighan's algorithm.
Time: O(set bits), Space: O(1)
Faster when few bits are set.
"""
count = 0while n:
n &= n - 1# Clear rightmost set bit
count += 1return count
defcount_bits_builtin(n: int) -> int:
"""Use Python built-in."""returnbin(n).count('1')
Single Number Problems (XOR)
from typing importListdefsingle_number(nums: List[int]) -> int:
"""
Find element appearing once (others appear twice).
Key insight: a ^ a = 0, a ^ 0 = a
Time: O(n), Space: O(1)
"""
result = 0for num in nums:
result ^= num
return result
defsingle_number_two(nums: List[int]) -> int:
"""
Find element appearing once (others appear 3 times).
Count bits mod 3 for each position.
Time: O(32n) = O(n), Space: O(1)
"""
result = 0for i inrange(32):
bit_sum = sum((num >> i) & 1for num in nums)
if bit_sum % 3:
result |= (1 << i)
# Handle negative numbers in Pythonif result >= (1 << 31):
result -= (1 << 32)
return result
defsingle_number_three(nums: List[int]) -> List[int]:
"""
Find two elements appearing once (others appear twice).
Time: O(n), Space: O(1)
"""
xor_all = 0for num in nums:
xor_all ^= num
# Get rightmost set bit (differs between the two singles)
diff_bit = xor_all & (-xor_all)
a = b = 0for num in nums:
if num & diff_bit:
a ^= num
else:
b ^= num
return [a, b]
Hamming Distance
defhamming_distance(x: int, y: int) -> int:
"""
Count differing bit positions.
Time: O(log n), Space: O(1)
"""
xor = x ^ y
count = 0while xor:
xor &= xor - 1
count += 1return count
defhamming_weight(n: int) -> int:
"""Count number of 1 bits (population count)."""return count_bits_kernighan(n)
Subset Generation
defgenerate_subsets_bitmask(nums: List[int]) -> List[List[int]]:
"""
Generate all subsets using bitmask enumeration.
Each integer 0 to 2^n-1 represents a subset.
Time: O(2^n * n), Space: O(1) per subset
"""
result = []
n = len(nums)
for mask inrange(1 << n): # 0 to 2^n - 1
subset = []
for i inrange(n):
if mask & (1 << i):
subset.append(nums[i])
result.append(subset)
return result
defiterate_subsets_of_mask(mask: int):
"""
Iterate all submasks of a bitmask.
Useful for bitmask DP.
Time: O(3^popcount(mask))
"""
submask = mask
while submask > 0:
yield submask
submask = (submask - 1) & mask
yield0# Empty subset
Common Bit Tricks
# Swap without temp variabledefswap(a: int, b: int) -> tuple:
a ^= b
b ^= a
a ^= b
return a, b
# Check if opposite signsdefopposite_signs(x: int, y: int) -> bool:
return (x ^ y) < 0# Get absolute value (for 32-bit)defabs_bit(n: int) -> int:
mask = n >> 31return (n + mask) ^ mask
# Multiply by 2^kdefmultiply_power_of_2(n: int, k: int) -> int:
return n << k
# Divide by 2^kdefdivide_power_of_2(n: int, k: int) -> int:
return n >> k
□ Bit indices 0-indexed?
□ Handling negative numbers?
□ Operator precedence correct? (& before ==)
□ Using parentheses around bit ops?
Bit Operation Quick Reference
x & (x-1) → Clear rightmost set bit
x & -x → Isolate rightmost set bit
x | (1<<i) → Set i-th bit
x & ~(1<<i) → Clear i-th bit
x ^ (1<<i) → Toggle i-th bit
x & 1 → Check if odd
