Bit Manipulation

# test bit i
(x >> i) & 1
x & (1 << i)              # truthy, not necessarily 1

# set bit i
x |= 1 << i

# clear bit i
x &= ~(1 << i)

# toggle bit i
x ^= 1 << i

# set bit i to a given value v (0 or 1), branch free
x = (x & ~(1 << i)) | (v << i)

# extract the low k bits
x & ((1 << k) - 1)

# clear all bits above position i (inclusive)
x &= (1 << i) - 1

# clear all bits below position i (inclusive)
x &= ~((1 << (i + 1)) - 1)

x.bit_count()             # Python 3.10+, popcount
bin(x).count("1")         # older Python
x.bit_length()            # position of the highest set bit, 0 for x == 0
x & -x                    # lowest set bit as a value
(x & -x).bit_length() - 1 # index of the lowest set bit

def popcount_kernighan(x):
    """Loops once per SET bit, not once per bit."""
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

def iterate_set_bits(x):
    """Yield the index of every set bit, cheaply."""
    while x:
        low = x & -x
        yield low.bit_length() - 1
        x ^= low

Integer.bitCount(x);              // popcount
Integer.numberOfTrailingZeros(x); // index of the lowest set bit, 32 if x == 0
Integer.numberOfLeadingZeros(x);
Integer.highestOneBit(x);         // the value, not the index
Integer.reverse(x);
Integer.toBinaryString(x);
Long.bitCount(x);

__builtin_popcount(x);       // and __builtin_popcountll for 64-bit
__builtin_ctz(x);            // count trailing zeros, UNDEFINED for x == 0
__builtin_clz(x);            // count leading zeros, UNDEFINED for x == 0
std::popcount(x);            // C++20, well defined
std::bit_width(x);           // C++20, 1 + floor(log2 x)
std::has_single_bit(x);      // C++20, power-of-two test

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

def is_power_of_four(x):
    return x > 0 and (x & (x - 1)) == 0 and (x - 1) % 3 == 0

def next_power_of_two(x):
    """Smallest power of two >= x."""
    if x <= 1:
        return 1
    return 1 << (x - 1).bit_length()

def prev_power_of_two(x):
    return 1 << (x.bit_length() - 1) if x else 0

def round_up_multiple_of_pow2(x, k):
    """Round x up to a multiple of 2^k."""
    mask = (1 << k) - 1
    return (x + mask) & ~mask

def swap_no_temp(a, b):
    a ^= b
    b ^= a
    a ^= b
    return a, b

def single_number(nums):
    """Every element appears twice except one. XOR everything."""
    out = 0
    for x in nums:
        out ^= x
    return out

def single_number_two_singles(nums):
    """Exactly two elements appear once. Split by a differing bit."""
    xor_all = 0
    for x in nums:
        xor_all ^= x
    low = xor_all & -xor_all              # a bit where the two answers differ
    a = b = 0
    for x in nums:
        if x & low:
            a ^= x
        else:
            b ^= x
    return [a, b]

def single_number_three_times(nums):
    """Every element appears three times except one. Count bits mod 3."""
    ones = twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos
        twos = (twos ^ x) & ~ones
    return ones

def missing_number(nums):
    """0..n with one missing. XOR indices against values."""
    out = len(nums)
    for i, x in enumerate(nums):
        out ^= i ^ x
    return out

def find_duplicate_and_missing(nums):
    """1..n where one value repeats and one is missing."""
    xor_all = 0
    for i, x in enumerate(nums, 1):
        xor_all ^= i ^ x
    low = xor_all & -xor_all
    a = b = 0
    for x in list(nums) + list(range(1, len(nums) + 1)):
        if x & low:
            a ^= x
        else:
            b ^= x
    return (a, b) if nums.count(a) > 1 else (b, a)

def xor_prefix_range(a, b):
    """XOR of all integers in [a, b] using a closed form for [0, n]."""
    def upto(n):
        return [n, 1, n + 1, 0][n % 4]
    return upto(b) ^ upto(a - 1)

def all_subsets(items):
    """Enumerate all 2^n subsets. O(2^n * n)."""
    n = len(items)
    out = []
    for mask in range(1 << n):
        out.append([items[i] for i in range(n) if (mask >> i) & 1])
    return out

def submasks(mask):
    """Every submask of mask, in decreasing order. Total work over all
    masks is O(3^n), not O(4^n)."""
    sub = mask
    while True:
        yield sub
        if sub == 0:
            break
        sub = (sub - 1) & mask

def count_bits_dp(n):
    """Popcount for 0..n in O(n). dp[i] = dp[i >> 1] + (i & 1)."""
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

def gray_code(n):
    """A sequence where consecutive entries differ by exactly one bit."""
    return [i ^ (i >> 1) for i in range(1 << n)]

def min_cost_assignment(cost):
    """n workers to n jobs, minimum total. Bitmask DP, O(2^n * n)."""
    n = len(cost)
    INF = float("inf")
    dp = [INF] * (1 << n)
    dp[0] = 0
    for mask in range(1 << n):
        if dp[mask] == INF:
            continue
        i = bin(mask).count("1")           # next worker to assign
        if i == n:
            continue
        for j in range(n):
            if not (mask >> j) & 1:
                nm = mask | (1 << j)
                dp[nm] = min(dp[nm], dp[mask] + cost[i][j])
    return dp[(1 << n) - 1]

MASK = 0xFFFFFFFF
INT_MIN, INT_MAX = -(1 << 31), (1 << 31) - 1

def to_signed_32(x):
    """Interpret the low 32 bits as a signed value."""
    x &= MASK
    return x - (1 << 32) if x >= 1 << 31 else x

def add_without_plus(a, b):
    """XOR is the sum without carry, AND << 1 is the carry."""
    while b:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
    return to_signed_32(a)

def reverse_bits_32(x):
    out = 0
    for _ in range(32):
        out = (out << 1) | (x & 1)
        x >>= 1
    return out

// Java: >>> is the logical shift, >> keeps the sign
int reverseBits(int x) {
    int out = 0;
    for (int i = 0; i < 32; i++) {
        out = (out << 1) | (x & 1);
        x >>>= 1;                    // MUST be >>>, or negatives loop forever
    }
    return out;
}
// Left-shifting into the sign bit is defined in Java, undefined in C++.