Bit Tricks: Flags, XOR and Clearing the Lowest Bit

Bits are the real data. 13 is 1101 in binary: one 8, one 4, no 2, one 1. Four operators work on every switch at once: & (both on), | (either on), ^ (exactly one on) and ~ (flip). Shifts move the row: x << k multiplies by 2^k and x >> k divides by 2^k, rounding down.

One switch at a time. Build a mask with 1 << i. Then: test x & (1 << i), set x | (1 << i), clear x & ~(1 << i), toggle x ^ (1 << i). Permissions work this way: READ = 1 << 0, WRITE = 1 << 1, ADMIN = 1 << 2; flags |= READ | ADMIN grants two rights in one number.

READ, WRITE, ADMIN = 1 << 0, 1 << 1, 1 << 2
flags = 0
flags |= READ | ADMIN      # 0b101
bool(flags & WRITE)        # False
bool(flags & ADMIN)        # True
flags ^= ADMIN             # toggle: back to 0b1

Clear the lowest 1. n & (n - 1) switches off the lowest set bit, because subtracting 1 flips that bit to 0 and every bit below it to 1. That one line counts set bits (repeat until zero: 0b101101 has 4) and tests for a power of two (only one bit is set, so the result is 0: n > 0 and n & (n - 1) == 0). n & -n keeps only the lowest set bit (12 & -12 is 4).

def count_bits(n):
    total = 0
    while n:
        n &= n - 1       # clears the lowest set bit
        total += 1
    return total

count_bits(0b101101)       # 4

XOR cancels. a ^ a is 0 and a ^ 0 is a, and XOR does not care about order. So XOR-ing a whole list in which every value appears twice except one leaves exactly the odd one out: 4 ^ 1 ^ 2 ^ 1 ^ 2 is 4, with no dictionary and no extra memory.

Every subset as a number. For n items, the numbers 0 ... 2^n - 1 are all the ways to pick a subset: bit i of the mask says whether item i is in. for mask in range(1 << n) visits all 2^n subsets (8 for 3 items), which is the engine of small brute-force and bitmask-DP problems.

Python-specific care. Python integers never overflow and negatives behave as if they had infinitely many leading 1s. To get a fixed 32-bit view, mask the result: -1 & 0xFFFFFFFF is 4294967295. Shifting a negative number right keeps it negative. Precedence is a trap: == binds tighter than &, so write (x & 1) == 1 with brackets.

Where it runs in production. Feature flags and permission sets, bitmaps that track millions of yes/no facts in a few kilobytes, Bloom filters (many bits set by several hash functions), IP subnet masks, and compact encodings in network protocols.