Bits, bytes, and bitwise tricks

You already know from how computers store data that everything in memory is binary. This post goes one level deeper: the actual operations CPUs perform directly on those bits, and the tricks built on top of them. Bitwise operations are O(1) — the fastest thing a computer can do — which is why they show up constantly in performance-critical code, flags/permissions systems, hashing, and interview problems.

Number systems: binary, decimal, hex

Converting decimal to binary: repeatedly divide by 2 and read the remainders bottom-up. Converting binary to decimal: sum bit × 2^position for every set bit, counting positions from the right starting at 0.

13 in binary:
13 / 2 = 6 remainder 1
 6 / 2 = 3 remainder 0
 3 / 2 = 1 remainder 1
 1 / 2 = 0 remainder 1
Read remainders bottom-up: 1101

Check: 1×8 + 1×4 + 0×2 + 1×1 = 8+4+0+1 = 13 ✓

The bitwise operators

Each operator works bit by bit, independently, on corresponding positions of two numbers.

Try it yourself — flip bits in A and B below and switch operations to see the result update live:

• AND (&) — masking: force certain bits to 0 while keeping others. x & 1 isolates the last bit (checks even/odd).
• OR (|) — setting bits: force certain bits to 1 without disturbing others.
• XOR (^) — toggling: flip specific bits; also the basis of “find the odd one out” and swapping without a temp variable.
• NOT (~) — flips every bit (in two’s complement, ~x equals -x - 1).
• Left shift (<<) — shifts bits left, filling with 0s on the right; equivalent to multiplying by 2^k.
• Right shift (>>) — shifts bits right; equivalent to dividing by 2^k (integer division, rounding toward negative infinity for signed numbers in most languages).

x = 0b1010    # 10
y = 0b0110    # 6

print(bin(x & y))   # 0b0010 → 2   (AND)
print(bin(x | y))   # 0b1110 → 14  (OR)
print(bin(x ^ y))   # 0b1100 → 12  (XOR)
print(bin(x << 1))  # 0b10100 → 20 (x * 2)
print(bin(x >> 1))  # 0b0101 → 5   (x / 2)

Negative numbers: two’s complement

Computers don’t store a “minus sign” — negative integers use two’s complement: to negate a number, flip all bits and add 1. The leftmost bit acts as a sign indicator (1 = negative) but is not simply “worth −1”; the whole pattern is reinterpreted.

# 8-bit two's complement
 5 = 00000101
-5 = 11111011   # flip all bits of 5 (11111010), then add 1

# Why this works: 00000101 + 11111011 = 100000000
# The 9th bit overflows off an 8-bit register, leaving 00000000 = 0
# So 11111011 behaves exactly like -5 under addition.

Why two’s complement and not “sign + magnitude”? Because addition/subtraction circuitry doesn’t need special-casing for signs — 5 + (-5) is just binary addition that happens to overflow to zero. It also gives exactly one representation of 0 (sign+magnitude has both +0 and -0).

Classic bit tricks

These come up constantly — memorize the pattern, not just the code:

n = 42

# Check if bit i is set
def is_set(n, i):
    return (n >> i) & 1 == 1

# Set bit i to 1
def set_bit(n, i):
    return n | (1 << i)

# Clear bit i (force to 0)
def clear_bit(n, i):
    return n & ~(1 << i)

# Toggle bit i
def toggle_bit(n, i):
    return n ^ (1 << i)

# Check if n is a power of two (exactly one bit set)
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
    # n-1 flips the lowest set bit and everything below it to 1;
    # ANDing with n clears that lowest bit. If n had only one bit
    # set, the result is 0.

# Count set bits (population count / Hamming weight)
def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1   # clears the lowest set bit each iteration
        count += 1
    return count       # runs once per SET bit, not once per bit — faster than checking all 32/64 bits

# Get the lowest set bit (useful in Fenwick trees, later in this series)
def lowest_set_bit(n):
    return n & (-n)   # -n is two's complement negation

# Swap two variables without a temp (XOR swap — mostly a curiosity today,
# real code should just use a temp variable or tuple unpacking, but the
# trick shows how XOR is its own inverse)
def xor_swap(a, b):
    a ^= b
    b ^= a   # b = original a
    a ^= b   # a = original b
    return a, b

Why n & (n - 1) clears the lowest set bit: subtracting 1 flips the lowest set bit to 0 and every bit below it (which were 0) to 1. ANDing with the original n keeps everything above the lowest set bit unchanged, zeroes the lowest set bit itself (since n had 1 there but n-1 has 0), and zeroes everything below (since n had 0s there).

n     = 0b10110100
n - 1 = 0b10110011   ← lowest set bit (the 4s place) flipped to 0, bits below flipped to 1
n & (n-1) = 0b10110000   ← lowest set bit cleared

Where bit manipulation shows up later in this series

# Fenwick tree (Binary Indexed Tree) — uses lowbit = i & (-i)
# Union-Find — sometimes packs rank + parent into one int
# Bitmask DP — represents "which items are chosen" as a bitmask
# Hash functions — rely on XOR and shifts for good bit distribution
subset_mask = 0b0000
subset_mask |= (1 << 3)   # include item 3 in the subset

// Flags/permissions systems (Unix file permissions, feature flags)
#define READ    (1 << 0)   // 0b001
#define WRITE   (1 << 1)   // 0b010
#define EXECUTE (1 << 2)   // 0b100

int perms = READ | WRITE;          // grant read+write
int can_write = perms & WRITE;     // check write permission

Key takeaways

1. Bitwise ops are O(1) — they operate on a fixed number of bits regardless of the “value” of the number.
2. AND masks, OR sets, XOR toggles, shifts multiply/divide by powers of two.
3. Two’s complement lets negative numbers use ordinary binary addition circuitry — negate by flipping all bits and adding 1.
4. n & (n-1) clears the lowest set bit — the basis of power-of-two checks and efficient set-bit counting.
5. n & (-n) isolates the lowest set bit — this exact trick powers Fenwick trees later in this series.
6. These tricks aren’t just interview trivia — they underlie hashing, flag/permission systems, and several data structures coming up later (Fenwick trees, bitmask DP, Bloom filters).

Practice problems

• Number of 1 Bits (Easy) — Hamming weight using n & (n-1)
• Single Number (Easy) — XOR trick to find the non-duplicate
• Power of Two (Easy) — n & (n-1) == 0 check
• Counting Bits (Easy) — DP + bit tricks combined

What’s next

• Arrays: fixed-size and indexing — putting the memory-access formula into practice
• Dynamic arrays — how list.append() uses the amortized doubling from the previous post (coming soon)