Bit Manipulation

# Basic operators
a & b   # AND: 1 only if both bits are 1
a | b   # OR: 1 if either bit is 1
a ^ b   # XOR: 1 if bits are different
~a      # NOT: flip all bits
a << n  # Left shift: multiply by 2^n
a >> n  # Right shift: divide by 2^n

# Check if nth bit is set
(num >> n) & 1

# Set nth bit
num | (1 << n)

# Clear nth bit
num & ~(1 << n)

# Toggle nth bit
num ^ (1 << n)

# Check if power of 2
n > 0 and (n & (n - 1)) == 0

# Get lowest set bit
n & (-n)

# Clear lowest set bit
n & (n - 1)

# Count set bits (Brian Kernighan)
count = 0
while n:
    n &= n - 1
    count += 1

def single_number(nums):
    """Find element that appears once (others twice)"""
    result = 0
    for num in nums:
        result ^= num
    return result

# XOR properties: a ^ a = 0, a ^ 0 = a, commutative

def count_bits(n):
    """Count set bits for all numbers 0 to n"""
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i >> 1] + (i & 1)
    return result

def subsets(nums):
    """Generate all subsets using bitmask"""
    n = len(nums)
    result = []
    
    for mask in range(1 << n):  # 2^n subsets
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)
    
    return result

def missing_number(nums):
    """Find missing number in [0, n]"""
    n = len(nums)
    result = n  # Start with n (might be missing)
    
    for i, num in enumerate(nums):
        result ^= i ^ num
    
    return result

def reverse_bits(n):
    """Reverse bits of 32-bit unsigned integer"""
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

def can_partition(nums):
    """Subset sum using bitset DP"""
    bits = 1  # bits represents reachable sums
    
    for num in nums:
        bits |= bits << num
    
    total = sum(nums)
    return total % 2 == 0 and (bits >> (total // 2)) & 1