Bit manipulation

Every integer in your program is, underneath, a fixed row of bits - for a byte, eight switches that are each 0 or 1. Decimal hides that, but the CPU never forgets it. Bitwise operators let you touch all eight switches at once, in parallel, in one instruction: test a flag, pack a set into a single number, swap two variables with no temporary, count the ones. Learn three verbs - mask, shift, XOR - and a surprising amount of low-level work collapses into a single line.

Eight switches, six operators

Write a byte with the most-significant bit on the left, so position $i$ is worth $2^i$. The value $172$ is 10101100: $128+32+8+4$. The four logical operators act bit-by-bit, and their entire behaviour fits in one small table - every column is decided independently, one row of switches at a time:

NOT (~) needs no table - it flips every bit, so ~00001111 becomes 11110000. The two shifts slide the whole pattern sideways: x << 1 moves every bit up one place - the same as multiplying by two - and the top bit falls off the byte's edge; x >> 1 moves everything down, halving the value and dropping the lowest bit. Shifting by $k$ multiplies or divides by $2^k$, which is why x << 3 is a fast x * 8.

Flip the bits yourself

Two 8-bit operands, A (teal) and B (amber). Click any bit in the A or B row to flip it between 0 and 1, and watch all six results recompute at once - in binary and decimal. The columns line up, so you can read each logical operator straight down. Then take the challenge: build a mask that isolates A's lowest set bit.

The tricks, in code

Each idiom below is a single expression doing what would otherwise be a loop or a temporary variable. The &=, |=, ^= forms are in-place versions of the operators you just watched.

# --- Masks: edit one bit at position i (see the "one mask, four verbs" callout)
set_bit    = x | (1 << i)     # force bit i to 1
clear_bit  = x & ~(1 << i)    # force bit i to 0
toggle_bit = x ^ (1 << i)     # flip bit i
test_bit   = (x >> i) & 1       # read bit i as 0 or 1

# --- XOR swap: exchange two values with no temporary
a ^= b; b ^= a; a ^= b        # each XOR cancels one operand back out

# --- Single number: every value appears twice except one
def single(nums):
    r = 0
    for v in nums:
        r ^= v                # pairs cancel: v ^ v == 0, v ^ 0 == v
    return r                  # the lone survivor

# --- Count set bits (Kernighan: one pass per 1-bit, not per bit)
def popcount(x):
    c = 0
    while x:
        x &= x - 1            # clears the lowest set bit each pass
        c += 1
    return c

# --- Power of two? exactly one bit set
is_pow2 = x > 0 and (x & (x - 1)) == 0

Check yourself