Bit Manipulation

# ===== 1) Set, clear, toggle, test =====
def set_bit(x, i):    return x |  (1 << i)
def clear_bit(x, i):  return x & ~(1 << i)
def toggle_bit(x, i): return x ^  (1 << i)
def test_bit(x, i):   return (x >> i) & 1

# ===== 2) Lowest set bit — isolate / count =====
# x & -x gives a mask with ONLY the lowest set bit
def lowest_bit(x): return x & -x
# Strip lowest bit
def strip_lowest(x): return x & (x - 1)
# Brian Kernighan popcount — count set bits by stripping lowest
def popcount(x):
    n = 0
    while x:
        x &= x - 1; n += 1
    return n
# Python has int.bit_count() since 3.10; same idea

# ===== 3) Is it a power of two? =====
def is_pow2(x): return x > 0 and (x & (x - 1)) == 0

# ===== 4) Iterate all subsets of a bitmask (downwards) =====
# Classic in bitmask DP — enumerate every sub-mask of mask in O(3^N) total over all masks
def subsets(mask):
    s = mask
    while s > 0:
        yield s
        s = (s - 1) & mask
    yield 0

# ===== 5) Iterate the set bits =====
def set_bits(x):
    while x:
        i = (x & -x).bit_length() - 1
        yield i
        x &= x - 1

# ===== 6) Swap two ints without temp =====
def swap_xor(a, b):
    a ^= b; b ^= a; a ^= b
    return a, b

# ===== 7) Find the one number that appears once when others appear twice =====
def lonely(nums):
    out = 0
    for x in nums: out ^= x
    return out

# ===== 8) Add two ints using only bit ops =====
def add(a, b, mask=(1 << 32) - 1):
    while b:
        carry = ((a & b) << 1) & mask
        a = (a ^ b) & mask
        b = carry
    return a

# ===== 9) Bitmask DP — travelling salesman over 16 cities =====
def tsp(dist):
    n = len(dist)
    inf = float('inf')
    dp = [[inf] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for u in range(n):
            if not (mask >> u) & 1: continue
            if dp[mask][u] == inf: continue
            for v in range(n):
                if (mask >> v) & 1: continue
                nmask = mask | (1 << v)
                nd = dp[mask][u] + dist[u][v]
                if nd < dp[nmask][v]: dp[nmask][v] = nd
    return min(dp[(1 << n) - 1][u] + dist[u][0] for u in range(n))

# ===== 10) Set operations as bitmasks =====
# - Union:        a | b
# - Intersection: a & b
# - Difference:   a & ~b
# - Symmetric diff: a ^ b
# - Contains i?:  (a >> i) & 1

# ===== 11) Common pitfalls =====
# - Signed integers wraparound: in C/C++/Java, mask with 0xFFFFFFFF when needed
# - Python ints are unbounded; tasks that need 32-bit must mask explicitly
# - Forgetting that a > 0 in is_pow2 (otherwise 0 reports as power of two)
# - Off-by-one with bit positions (i from 0 = LSB)

# ===== 12) When NOT to use bit tricks =====
# - Code that future you must read and debug under pressure
# - Languages without strong integer types (JS bitwise truncates to 32-bit signed)
# - Reach for plain code; reach for bits only when the perf or the algorithm needs it

// Common tricks
x & (x - 1)        // turns off the lowest set bit
x & -x             // isolates the lowest set bit
x ^ y              // bits set in exactly one of x, y
((x >> i) & 1)     // get the i-th bit