Bit Manipulation

Bit Manipulation

# Common operations
n = 0b1010  # 10

n & 1           # check if odd:  1 if odd, 0 if even
n >> 1          # divide by 2
n << 1          # multiply by 2
n & (n-1)       # clear lowest set bit
n & (-n)        # isolate lowest set bit
n ^ n           # XOR with self = 0
a ^ b ^ a       # = b  (cancel duplicates)

# Count set bits (Hamming weight)
def count_bits(n):
    count = 0
    while n:
        n &= n-1  # clear lowest set bit
        count += 1
    return count

# Single number (all others appear twice)
def single_number(nums):
    return eval('^'.join(map(str,nums)))  # XOR all
    # a ^ a = 0, so duplicates cancel

# Power of two
def is_power_of_two(n):
    return n>0 and (n & n-1)==0

# Subsets using bitmask
def all_subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1<>i & 1]
        result.append(subset)
    return result