Bit masks, bitsets and number theory

Bit masks encode membership in bit positions. Set with mask|1<<i, test with mask&(1<<i), clear with mask&~(1<<i). Python integers are unbounded; restrict complements explicitly for a fixed-width universe.

x&−x isolates the lowest set bit; x&(x−1) clears it. Submask enumeration uses s=(s−1)&mask and must stop after0. XOR cancels pairs only under the appropriate multiplicity contract.

Bitsets parallelise Boolean work within machine words but large bitsets cost proportional to word count. Euclid computes GCD via remainders, and modular exponentiation follows exponent bits. Modulo and overflow assumptions matter in hashing and arithmetic.

def submasks(mask):
    if mask < 0: raise ValueError("nonnegative mask required")
    s=mask
    while True:
        yield s
        if s == 0: break
        s=(s-1)&mask
assert list(submasks(10)) == [10,8,2,0]