Bit Manipulation: Thinking Close to Hardware

Chapter 34: Bit Manipulation — Thinking Close to Hardware

When you write if x % 2 == 0 to check parity, the CPU actually checks whether the lowest bit of x is 0. When you write x * 2, the CPU actually shifts all bits of x left by one position. Programming languages give you the abstraction of "numbers," but at the hardware level, everything is bits — sequences of 0s and 1s.

Bit manipulation is operating directly on bits. These operations are faster than arithmetic (typically 1 CPU cycle), but unintuitive for humans. Mastering bit manipulation provides value at three levels:

1. Writing more efficient code: Replace expensive division and modulo with bit operations
2. Understanding low-level systems: OS, network protocols, and crypto all use bit manipulation extensively
3. Solving specific algorithm problems: Some problems (like "single number") achieve O(1) space with bit tricks

Level 1 · What You Need to Know

1.1 The Six Basic Bit Operations

# Basic bit operation demo
a = 0b1100  # 12
b = 0b1010  # 10

print(f"a & b  = {bin(a & b)}")   # 0b1000 = 8
print(f"a | b  = {bin(a | b)}")   # 0b1110 = 14
print(f"a ^ b  = {bin(a ^ b)}")   # 0b0110 = 6
print(f"~a     = {bin(~a & 0xF)}")  # 0b0011 = 3 (4-bit)
print(f"a << 1 = {bin(a << 1)}")  # 0b11000 = 24
print(f"a >> 1 = {bin(a >> 1)}")  # 0b110 = 6

1.2 The Magic Properties of XOR

XOR (exclusive or) is the most magical bit operation because it simultaneously has multiple useful properties:

# XOR algebraic properties
# 1. Self-inverse: a ^ a = 0 (any number XOR itself equals 0)
# 2. Identity: a ^ 0 = a (any number XOR 0 equals itself)
# 3. Commutative: a ^ b = b ^ a
# 4. Associative: (a ^ b) ^ c = a ^ (b ^ c)

# These properties combined mean:
# XOR-ing a group of numbers: order doesn't matter, pairs cancel out

# Application 1: Swap two numbers without temporary variable
def swap_xor(a: int, b: int) -> tuple[int, int]:
    """Swap two numbers using XOR (no temporary variable)"""
    a = a ^ b
    b = a ^ b  # b = (a^b)^b = a
    a = a ^ b  # a = (a^b)^a = b (b is now original a)
    return a, b

x, y = 5, 3
x, y = swap_xor(x, y)
print(f"After swap: x={x}, y={y}")  # x=3, y=5

# Application 2: Find the single number
def single_number(nums: list[int]) -> int:
    """
    All numbers appear twice except one. Find it.
    LeetCode #136
    
    Principle: a ^ a = 0, 0 ^ b = b
    All pairs cancel, leaving the unique number
    """
    result = 0
    for num in nums:
        result ^= num
    return result

print(single_number([2, 1, 4, 1, 2]))  # 4

1.3 Common Bit Manipulation Tricks

# Trick 1: Check parity
def is_even(n: int) -> bool:
    """n & 1 == 0 means even"""
    return (n & 1) == 0

# Trick 2: Multiply/divide by powers of 2
def multiply_power_of_2(n: int, k: int) -> int:
    """n * 2^k = n << k"""
    return n << k

def divide_power_of_2(n: int, k: int) -> int:
    """n // 2^k = n >> k (positive integers only)"""
    return n >> k

# Trick 3: Check if power of 2
def is_power_of_two(n: int) -> bool:
    """
    LeetCode #231
    Powers of 2 have exactly one 1 bit: 1, 10, 100, 1000, ...
    n & (n-1) clears the lowest set bit
    If result is 0, there was only one 1 bit
    """
    return n > 0 and (n & (n - 1)) == 0

# Trick 4: Get lowest set bit (lowbit)
def lowest_bit(n: int) -> int:
    """
    n & (-n) or n & (~n + 1)
    Result contains only the lowest 1 bit of n
    Example: n = 12 (1100), lowest_bit = 4 (0100)
    
    Why: -n in two's complement is ~n + 1
    ~1100 + 1 = 0011 + 1 = 0100
    1100 & 0100 = 0100
    """
    return n & (-n)

# Trick 5: Clear lowest set bit
def clear_lowest_bit(n: int) -> int:
    """
    n & (n-1) clears the lowest 1 bit
    Example: n = 12 (1100), n-1 = 11 (1011)
    1100 & 1011 = 1000
    """
    return n & (n - 1)

# Trick 6: Get k-th bit
def get_bit(n: int, k: int) -> int:
    """Get the k-th bit of n (0-indexed)"""
    return (n >> k) & 1

# Trick 7: Set k-th bit to 1
def set_bit(n: int, k: int) -> int:
    """Set the k-th bit of n to 1"""
    return n | (1 << k)

# Trick 8: Clear k-th bit
def clear_bit(n: int, k: int) -> int:
    """Set the k-th bit of n to 0"""
    return n & ~(1 << k)

# Trick 9: Toggle k-th bit
def toggle_bit(n: int, k: int) -> int:
    """Flip the k-th bit of n"""
    return n ^ (1 << k)


# Demo
print(f"12 is even: {is_even(12)}")           # True
print(f"5 * 8 = {multiply_power_of_2(5, 3)}")  # 40
print(f"16 is power of 2: {is_power_of_two(16)}")  # True
print(f"lowest_bit(12) = {lowest_bit(12)}")      # 4
print(f"clear_lowest_bit(12) = {clear_lowest_bit(12)}")  # 8

1.4 Bit Operation Quick Reference

1.5 Common Mistakes

Mistake 1: Python's unlimited precision integer trap

# Python integers have arbitrary precision; ~ doesn't produce fixed-width results like C
n = 5  # 101
print(~n)  # -6, not the "flip to 010" you might expect

# For 32-bit flip:
def flip_32bit(n: int) -> int:
    return n ^ 0xFFFFFFFF

print(flip_32bit(5))  # 4294967290 (unsigned)

Mistake 2: Shift overflow

# In C/Java, left shift can overflow
# Python won't overflow, but beware when submitting C++ in contests
# int32: 1 << 31 is negative! Use 1LL << 31 or unsigned

# Safe approach in Python
def safe_left_shift(n: int, k: int, bits: int = 32) -> int:
    """Simulate fixed-width left shift"""
    mask = (1 << bits) - 1
    return (n << k) & mask

Mistake 3: Operator precedence

# Bit operations have LOWER precedence than comparison! Common bug source
n = 5
# Wrong: if n & 1 == 0  actually is  if n & (1 == 0)  i.e.  if n & 0
# Correct: if (n & 1) == 0
print(n & 1 == 0)    # False (1==0 is False=0, 5&0=0, but Python special handling)
print((n & 1) == 0)  # False (this correctly checks "is 5 even?")

Level 2 · How It Works Under the Hood

2.1 Brian Kernighan's Algorithm — Counting Set Bits

Problem: Given an integer n, count how many 1s are in its binary representation (called popcount or Hamming weight).

Naive method: Check each bit, O(bit width) = O(32) or O(64).

Brian Kernighan's method: Clear the lowest set bit each iteration until zero. Loop count = number of 1s.

def count_bits_kernighan(n: int) -> int:
    """
    Brian Kernighan's algorithm: count 1 bits in binary
    LeetCode #191: Number of 1 Bits
    
    Core: n & (n-1) clears the lowest set bit
    Loop count = number of 1 bits
    
    Time: O(k), k = number of 1 bits (worst O(log n) = O(bit width))
    
    Source: Brian Kernighan introduced this in "The C Programming Language" (K&R, 1978)
    The trick was actually published earlier by Peter Wegner in 1960
    """
    count = 0
    while n:
        n &= (n - 1)  # Clear lowest set bit
        count += 1
    return count


# Why does n & (n-1) clear the lowest set bit?
# Suppose n = ...1000 (lowest 1 followed by zeros)
# Then n-1 = ...0111 (lowest 1 becomes 0, zeros below become 1)
# n & (n-1) = ...0000 (lowest 1 and everything below it cleared)

# Demo
for n in [0, 1, 7, 12, 128, 255]:
    print(f"n={n:3d} ({bin(n):>10s}): {count_bits_kernighan(n)} ones")

Lookup table method (faster O(1) implementation):

# Precompute popcount for each byte (0-255)
POPCOUNT_TABLE = [0] * 256
for i in range(1, 256):
    POPCOUNT_TABLE[i] = POPCOUNT_TABLE[i >> 1] + (i & 1)

def count_bits_table(n: int) -> int:
    """
    Lookup table: O(1) time, requires 256-byte table
    Split 32-bit integer into 4 bytes, look up each, sum
    """
    count = 0
    while n:
        count += POPCOUNT_TABLE[n & 0xFF]
        n >>= 8
    return count


# Bit-parallel method (what CPUs actually use)
def count_bits_parallel(n: int) -> int:
    """
    Bit-parallel popcount: O(1) operations on 32-bit integer
    
    Idea: divide and conquer
    1. Count 1s in each 2-bit group
    2. Sum adjacent 2-bit groups into 4-bit groups
    3. Sum adjacent 4-bit groups into 8-bit groups
    4. ...until merged into one number
    
    This is the principle behind CPU's POPCNT instruction
    """
    n = n & 0xFFFFFFFF
    
    # Step 1: count in 2-bit groups
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555)
    # Step 2: count in 4-bit groups
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
    # Step 3: count in 8-bit groups
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
    # Step 4: count in 16-bit groups
    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF)
    # Step 5: final merge
    n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF)
    
    return n


# Verify consistency
for n in [0, 1, 7, 12, 128, 255, 0xDEADBEEF]:
    k = count_bits_kernighan(n)
    t = count_bits_table(n)
    p = count_bits_parallel(n)
    assert k == t == p, f"Inconsistent: n={n}"
    print(f"n={n:#010x}: popcount={k}")

2.2 Bitmaps

A bitmap uses one bit to represent one boolean value, saving over 200x space compared to Python's list[bool] (28 bytes per element).

class Bitmap:
    """
    Bitmap: stores one boolean per bit
    
    Applications:
    - Bloom Filter's underlying storage
    - OS page management (free/used)
    - Redis BITFIELD command
    - Large-scale deduplication (4 billion integers need only 512MB)
    """
    
    def __init__(self, size: int):
        """Create bitmap that can store 'size' bits"""
        self.size = size
        self.data = bytearray((size + 7) // 8)
    
    def set(self, pos: int):
        """Set bit at position pos to 1"""
        if 0 <= pos < self.size:
            self.data[pos >> 3] |= (1 << (pos & 7))
    
    def clear(self, pos: int):
        """Set bit at position pos to 0"""
        if 0 <= pos < self.size:
            self.data[pos >> 3] &= ~(1 << (pos & 7))
    
    def get(self, pos: int) -> bool:
        """Get bit value at position pos"""
        if 0 <= pos < self.size:
            return bool(self.data[pos >> 3] & (1 << (pos & 7)))
        return False
    
    def count_ones(self) -> int:
        """Count total number of set bits"""
        count = 0
        for byte in self.data:
            count += POPCOUNT_TABLE[byte]
        return count
    
    def memory_bytes(self) -> int:
        """Actual memory usage"""
        return len(self.data)


# Demo: deduplicating 4 billion integers
# Using set: 28 bytes each, 4B * 28 = 112 GB
# Using Bitmap: 4B / 8 = 500 MB

bm = Bitmap(100)
bm.set(0)
bm.set(42)
bm.set(99)
print(f"Bitmap size: {bm.memory_bytes()} bytes, storing {bm.size} bits")
print(f"Bit 0: {bm.get(0)}, Bit 42: {bm.get(42)}, Bit 50: {bm.get(50)}")
print(f"Total {bm.count_ones()} ones")

2.3 Subset Enumeration with Bit Operations

Problem: Given set {0, 1, ..., n-1}, enumerate all its subsets.

Each subset can be represented by an n-bit integer: bit i is 1 means element i is in the subset.

def enumerate_all_subsets(n: int):
    """
    Enumerate all subsets of n elements
    Each bit in an n-bit integer represents element presence
    Total: 2^n subsets
    """
    subsets = []
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(i)
        subsets.append(subset)
    return subsets


def enumerate_submasks(mask: int):
    """
    Enumerate all submasks of a given mask (subsets of a subset)
    
    Example: mask = 0b1101, submasks are:
    1101, 1100, 1001, 1000, 0101, 0100, 0001, 0000
    
    Trick: sub = (sub - 1) & mask iterates all submasks from mask down
    
    Time: O(2^popcount(mask))
    """
    submasks = []
    sub = mask
    while sub > 0:
        submasks.append(sub)
        sub = (sub - 1) & mask
    submasks.append(0)  # empty set
    return submasks


# Demo
print("All subsets of {0,1,2}:")
for subset in enumerate_all_subsets(3):
    print(f"  {subset}")

print("\nAll submasks of 0b1101:")
for sub in enumerate_submasks(0b1101):
    print(f"  {bin(sub)}")

2.4 Bitmask Dynamic Programming

Bitmask DP uses bits of an integer to represent a set of boolean states, making "sets" a DP state dimension.

Classic Problem: Travelling Salesman Problem (TSP)

def tsp_bitmask(dist: list[list[int]]) -> int:
    """
    TSP: shortest path visiting all cities exactly once
    
    State: dp[mask][i] = shortest distance with visited set = mask, currently at city i
    Transition: dp[mask | (1<<j)][j] = min(dp[mask][i] + dist[i][j])
                where j is not in mask
    
    Time: O(2^n * n^2)
    Space: O(2^n * n)
    
    Applicable for: n <= 20 (2^20 = 1 million, beyond that memory explodes)
    """
    n = len(dist)
    INF = float('inf')
    
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start from city 0
    
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == INF:
                continue
            if not (mask & (1 << i)):
                continue
            
            for j in range(n):
                if mask & (1 << j):
                    continue  # j already visited
                new_mask = mask | (1 << j)
                new_dist = dp[mask][i] + dist[i][j]
                if new_dist < dp[new_mask][j]:
                    dp[new_mask][j] = new_dist
    
    full_mask = (1 << n) - 1
    result = INF
    for i in range(n):
        if dp[full_mask][i] + dist[i][0] < result:
            result = dp[full_mask][i] + dist[i][0]
    
    return result


# Demo
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(f"TSP shortest distance: {tsp_bitmask(dist)}")  # 80

Classic Problem: Maximum Independent Set

def max_independent_set(adj: list[list[int]]) -> int:
    """
    Maximum independent set: find most vertices with no two adjacent
    
    adj[i] = list of vertices adjacent to vertex i
    Use bitmask to represent "which vertices are selected"
    
    O(2^n * n)
    """
    n = len(adj)
    
    # Preprocess: adj_mask[i] = bitmask of all neighbors of i
    adj_mask = [0] * n
    for i in range(n):
        for j in adj[i]:
            adj_mask[i] |= (1 << j)
    
    max_size = 0
    
    for mask in range(1 << n):
        is_independent = True
        for i in range(n):
            if not (mask & (1 << i)):
                continue
            if mask & adj_mask[i]:
                is_independent = False
                break
        
        if is_independent:
            size = bin(mask).count('1')
            max_size = max(max_size, size)
    
    return max_size

2.5 Bit Operations in Permission Systems

Linux file permissions, database permissions, and user roles all use bit manipulation extensively:

# Linux file permission model
READ = 0b100    # 4
WRITE = 0b010   # 2
EXECUTE = 0b001 # 1

def check_permission(user_perm: int, required: int) -> bool:
    """Check if user has required permission"""
    return (user_perm & required) == required

def grant_permission(current: int, new_perm: int) -> int:
    """Grant new permission"""
    return current | new_perm

def revoke_permission(current: int, perm: int) -> int:
    """Revoke permission"""
    return current & ~perm

# Demo
user = READ | WRITE  # rwx = 110 = read+write
print(f"Has read: {check_permission(user, READ)}")       # True
print(f"Has execute: {check_permission(user, EXECUTE)}")  # False

user = grant_permission(user, EXECUTE)
print(f"After grant: {oct(user)}")  # 0o7 (rwx)

user = revoke_permission(user, WRITE)
print(f"After revoke: {oct(user)}")  # 0o5 (r-x)

Level 3 · What the Theory Says

3.1 Bit Operations at the CPU Instruction Level

In modern CPUs, bit operations are the most fundamental operations, implemented directly by hardware circuits:

AND gate: Output 1 only when both inputs are 1 (two transistors in series) OR gate: Output 1 when either input is 1 (two transistors in parallel) XOR gate: Output 1 when inputs differ (requires 4 NAND gates, ~8 transistors) NOT gate: Invert (1 transistor)

A 64-bit AND operation = 64 AND gates working in parallel, completed in 1 clock cycle.

Integer adder implementation is also based on bit operations:

• Half adder: sum = a ^ b, carry = a & b
• Full adder: sum = a ^ b ^ cin, cout = (a & b) | (cin & (a ^ b))
• 64-bit adder = 64 full adders in series (optimized with prefix adders in practice)

def add_without_plus(a: int, b: int) -> int:
    """
    Addition without the + operator (common interview question)
    
    Principle:
    - a ^ b = addition result without carries
    - (a & b) << 1 = carry
    - Repeat until carry is 0
    
    This is exactly how hardware adders work!
    """
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    
    a, b = a & MASK, b & MASK
    
    while b:
        carry = ((a & b) << 1) & MASK
        a = (a ^ b) & MASK
        b = carry
    
    # Handle negative numbers (two's complement)
    return a if a <= MAX_INT else ~(a ^ MASK)


# Demo
print(add_without_plus(5, 3))    # 8
print(add_without_plus(-1, 1))   # 0
print(add_without_plus(-5, -3))  # -8

3.2 Two's Complement Representation

Modern computers almost universally use two's complement for negative numbers. Understanding it is fundamental to understanding bit operations.

Two's complement definition (for n-bit integers):

• Positive numbers and zero: direct binary representation
• Negative number -x: represented as 2^n - x

Two's complement properties:

• Range: -2^(n-1) to 2^(n-1) - 1
• -1: all ones (0xFFFFFFFF)
• Minimum -2^(n-1): only MSB is 1 (1000...0)
• Negation: ~x + 1 (invert and add one)

def to_twos_complement(n: int, bits: int = 32) -> str:
    """Convert integer to n-bit two's complement binary"""
    if n >= 0:
        return format(n, f'0{bits}b')
    else:
        return format((1 << bits) + n, f'0{bits}b')

def from_twos_complement(binary: str) -> int:
    """Convert two's complement binary to integer"""
    bits = len(binary)
    n = int(binary, 2)
    if binary[0] == '1':  # negative
        n -= (1 << bits)
    return n

# Demo
for n in [5, -5, 0, -1, 127, -128]:
    tc = to_twos_complement(n, 8)
    back = from_twos_complement(tc)
    print(f"{n:4d} -> {tc} -> {back}")

Why does n & (-n) isolate the lowest set bit?

n    = ...XY10...0  (lowest 1 followed by zeros)
~n   = ...X'Y'01...1
~n+1 = ...X'Y'10...0  (this is -n in two's complement)
n & (-n) = 000010...0  (only the lowest 1 is preserved)

Because n and -n agree at the lowest set bit and complement each other above it.

3.3 SIMD — Single Instruction, Multiple Data

SIMD (Single Instruction, Multiple Data) provides vector instructions in modern CPUs that perform the same bit operation on multiple data simultaneously.

# SIMD concept demonstration (Python can't use SIMD directly)

# Without SIMD: process one element at a time
def add_arrays_scalar(a: list[int], b: list[int]) -> list[int]:
    """Scalar addition: 1 element per iteration"""
    return [x + y for x, y in zip(a, b)]

# With SIMD: process 4 elements simultaneously (SSE 128-bit register, 4x 32-bit int)
# In C/Rust:
# __m128i va = _mm_load_si128(a);
# __m128i vb = _mm_load_si128(b);
# __m128i vc = _mm_add_epi32(va, vb);  // One instruction adds 4 integers

# In Python, use NumPy to indirectly leverage SIMD
import numpy as np

def add_arrays_simd(a: np.ndarray, b: np.ndarray) -> np.ndarray:
    """NumPy uses SIMD under the hood"""
    return a + b

SIMD architecture evolution:

SIMD in string processing:

Modern strlen(), memcmp(), memchr() implementations all use SIMD:

• Load 16/32/64 bytes at once
• Compare all bytes in parallel against zero (or target character)
• Use bitmask to locate first match

def simd_style_memchr(data: bytes, target: int) -> int:
    """
    Simulates SIMD-style byte search
    Actual libc memchr uses SSE/AVX to compare 16-64 bytes at once
    """
    LANE_WIDTH = 16
    n = len(data)
    
    # Process in 16-byte blocks
    i = 0
    while i + LANE_WIDTH <= n:
        block = data[i:i+LANE_WIDTH]
        for j in range(LANE_WIDTH):
            if block[j] == target:
                return i + j
        i += LANE_WIDTH
    
    # Handle tail
    while i < n:
        if data[i] == target:
            return i
        i += 1
    
    return -1

3.4 Mathematical Theory of Bit Operations

Bit operations form a Boolean Algebra, axiomatized by George Boole in 1854, and proven implementable with circuits by Claude Shannon in his 1937 master's thesis.

Boolean algebra fundamental laws:

Additional XOR properties:

• a ^ a = 0 (self-inverse)
• a ^ 0 = a (identity)
• XOR forms an Abelian group (invertible: a ^ b ^ b = a)
• XOR is equivalent to addition in GF(2) (Galois field)

These mathematical properties explain why XOR is so important in cryptography: it's the only bitwise operation that is information-theoretically "perfect" — knowing the output and one input uniquely determines the other input.

3.5 Hamming Code — A Classic Application of Bit Operations

Richard Hamming's 1950 error-correcting code is one of the most elegant applications of bit manipulation in communication theory:

def hamming_encode(data: int, data_bits: int = 4) -> int:
    """
    Hamming(7,4) encoding: 4 data bits -> 7 encoded bits
    
    Position numbering: 1, 2, 3, 4, 5, 6, 7
    Parity bits: positions 1, 2, 4 (powers of 2)
    Data bits: positions 3, 5, 6, 7
    
    Parity rules:
    p1 covers positions 1,3,5,7 (positions with bit 0 set in binary)
    p2 covers positions 2,3,6,7 (positions with bit 1 set in binary)
    p4 covers positions 4,5,6,7 (positions with bit 2 set in binary)
    
    Hamming, "Error Detecting and Error Correcting Codes",
    Bell System Technical Journal, 1950
    """
    d1 = (data >> 3) & 1  # position 3
    d2 = (data >> 2) & 1  # position 5
    d3 = (data >> 1) & 1  # position 6
    d4 = data & 1         # position 7
    
    p1 = d1 ^ d2 ^ d4    # covers positions 3,5,7
    p2 = d1 ^ d3 ^ d4    # covers positions 3,6,7
    p4 = d2 ^ d3 ^ d4    # covers positions 5,6,7
    
    # Assemble 7-bit code: p1 p2 d1 p4 d2 d3 d4
    encoded = (p1 << 6) | (p2 << 5) | (d1 << 4) | (p4 << 3) | \
              (d2 << 2) | (d3 << 1) | d4
    
    return encoded


def hamming_decode(received: int) -> tuple[int, int]:
    """
    Hamming(7,4) decoding: detect and correct 1-bit errors
    
    Returns (data, error_position), error_position 0 means no error
    """
    bits = [(received >> i) & 1 for i in range(6, -1, -1)]
    
    # Syndrome bits
    s1 = bits[0] ^ bits[2] ^ bits[4] ^ bits[6]  # positions 1,3,5,7
    s2 = bits[1] ^ bits[2] ^ bits[5] ^ bits[6]  # positions 2,3,6,7
    s4 = bits[3] ^ bits[4] ^ bits[5] ^ bits[6]  # positions 4,5,6,7
    
    syndrome = (s4 << 2) | (s2 << 1) | s1
    
    # Correct error
    if syndrome != 0:
        error_pos = syndrome - 1  # convert to 0-indexed
        bits[error_pos] ^= 1  # flip error bit
    
    # Extract data bits (positions 3, 5, 6, 7 -> indices 2, 4, 5, 6)
    data = (bits[2] << 3) | (bits[4] << 2) | (bits[5] << 1) | bits[6]
    
    return data, syndrome


# Demo
original_data = 0b1011  # data = 11
encoded = hamming_encode(original_data)
print(f"Original data: {bin(original_data)}")
print(f"Encoded: {bin(encoded)}")

# Simulate 1-bit error
corrupted = encoded ^ (1 << 3)  # flip bit at position 4
print(f"Corrupted: {bin(corrupted)}")

decoded, error_pos = hamming_decode(corrupted)
print(f"Decoded: {bin(decoded)}, error position: {error_pos}")
print(f"Correction successful: {decoded == original_data}")

Level 4 · Edge Cases and Pitfalls

4.1 Interview Problem: Single Number I (LeetCode #136)

def single_number_136(nums: list[int]) -> int:
    """
    All numbers appear twice except one.
    XOR everything: pairs cancel, single remains.
    
    Time O(n), Space O(1)
    """
    result = 0
    for num in nums:
        result ^= num
    return result

print(single_number_136([4, 1, 2, 1, 2]))  # 4

4.2 Interview Problem: Single Number II (LeetCode #137)

def single_number_137(nums: list[int]) -> int:
    """
    All numbers appear three times except one.
    
    Approach: for each bit position, count total 1s across all numbers.
    If divisible by 3, the single number has 0 at that bit.
    Otherwise, it has 1.
    
    Time O(32n) = O(n), Space O(1)
    """
    result = 0
    for i in range(32):
        bit_sum = 0
        for num in nums:
            if num < 0:
                num = num & 0xFFFFFFFF
            bit_sum += (num >> i) & 1
        
        if bit_sum % 3 != 0:
            result |= (1 << i)
    
    if result >= (1 << 31):
        result -= (1 << 32)
    
    return result


# Method 2: finite state machine (more clever)
def single_number_137_v2(nums: list[int]) -> int:
    """
    Use two variables ones, twos to simulate a "modulo 3 counter"
    
    ones: tracks bits that appeared 1 time
    twos: tracks bits that appeared 2 times
    After 3 appearances: reset to 0
    
    State transitions (per bit):
    count = 0: ones=0, twos=0
    count = 1: ones=1, twos=0
    count = 2: ones=0, twos=1
    count = 3: ones=0, twos=0 (reset)
    """
    ones, twos = 0, 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones


# Tests
print(single_number_137([2, 2, 3, 2]))    # 3
print(single_number_137_v2([0, 1, 0, 1, 0, 1, 99]))  # 99

4.3 Interview Problem: Single Number III (LeetCode #260)

def single_number_260(nums: list[int]) -> list[int]:
    """
    All numbers appear twice except two (call them a and b).
    
    Approach:
    1. XOR all numbers to get a ^ b (pairs cancel)
    2. Any set bit in a ^ b means a and b differ at that position
    3. Use that bit to partition all numbers into two groups
    4. XOR each group separately to get a and b
    
    Time O(n), Space O(1)
    """
    # Step 1: get a ^ b
    xor_all = 0
    for num in nums:
        xor_all ^= num
    
    # Step 2: find any set bit in a ^ b (use lowbit)
    diff_bit = xor_all & (-xor_all)
    
    # Step 3: partition and XOR separately
    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num
    
    return [a, b]


# Test
result = single_number_260([1, 2, 1, 3, 2, 5])
print(f"Two single numbers: {sorted(result)}")  # [3, 5]

4.4 Interview Problem: Hamming Distance (LeetCode #461)

def hamming_distance(x: int, y: int) -> int:
    """
    Hamming distance = number of positions where corresponding bits differ
    
    Method: XOR then count set bits
    Bits that are 1 in x ^ y are the positions where x and y differ
    """
    xor = x ^ y
    count = 0
    while xor:
        xor &= (xor - 1)  # Brian Kernighan
        count += 1
    return count


def total_hamming_distance(nums: list[int]) -> int:
    """
    LeetCode #477: sum of Hamming distances of all pairs
    
    Trick: count bit by bit
    For each bit position, count how many numbers have 1: call it c
    That bit's contribution to total distance = c * (n - c)
    (c ones paired with (n-c) zeros)
    
    Time O(32n) = O(n)
    """
    n = len(nums)
    total = 0
    
    for i in range(32):
        ones = sum(1 for num in nums if (num >> i) & 1)
        total += ones * (n - ones)
    
    return total


# Tests
print(f"hamming(1, 4) = {hamming_distance(1, 4)}")  # 2 (001 vs 100)
print(f"total hamming [4,14,2] = {total_hamming_distance([4, 14, 2])}")  # 6

4.5 Interview Problem: Power of Two (#231) and Number of 1 Bits (#191)

def is_power_of_two(n: int) -> bool:
    """
    LeetCode #231
    n is power of 2 iff n > 0 and binary has exactly one 1
    """
    return n > 0 and (n & (n - 1)) == 0


def number_of_1_bits(n: int) -> int:
    """
    LeetCode #191
    Count 1 bits in unsigned integer's binary
    """
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count


# Advanced: count bits for all numbers 0 to n
def count_bits_all(n: int) -> list[int]:
    """
    LeetCode #338: Counting Bits
    Return [popcount(0), popcount(1), ..., popcount(n)]
    
    DP relation: popcount(x) = popcount(x >> 1) + (x & 1)
    i.e., x's 1-count = (x right-shifted by 1)'s 1-count + x's lowest bit
    
    Time O(n), Space O(n)
    """
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i >> 1] + (i & 1)
    return result


# Alternative DP: popcount(x) = popcount(x & (x-1)) + 1
def count_bits_all_v2(n: int) -> list[int]:
    """Using the clear-lowest-bit relation"""
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i & (i - 1)] + 1
    return result


# Tests
print(f"16 is power of 2: {is_power_of_two(16)}")  # True
print(f"18 is power of 2: {is_power_of_two(18)}")  # False
print(f"popcount(11) = {number_of_1_bits(11)}")  # 3
print(f"count_bits(5) = {count_bits_all(5)}")    # [0, 1, 1, 2, 1, 2]

4.6 More Bit Manipulation Interview Problems

def reverse_bits(n: int) -> int:
    """
    LeetCode #190: Reverse bits of a 32-bit unsigned integer
    
    Divide and conquer: swap adjacent 1-bit groups, then 2-bit,
    then 4-bit, 8-bit, 16-bit
    """
    n = ((n & 0x55555555) << 1) | ((n >> 1) & 0x55555555)
    n = ((n & 0x33333333) << 2) | ((n >> 2) & 0x33333333)
    n = ((n & 0x0F0F0F0F) << 4) | ((n >> 4) & 0x0F0F0F0F)
    n = ((n & 0x00FF00FF) << 8) | ((n >> 8) & 0x00FF00FF)
    n = ((n & 0x0000FFFF) << 16) | ((n >> 16) & 0x0000FFFF)
    return n


def missing_number(nums: list[int]) -> int:
    """
    LeetCode #268: Missing number from 0 to n
    
    Method: XOR all indices and all numbers
    Indices 0,1,...,n XOR'd with nums leaves the missing one
    """
    n = len(nums)
    result = n  # Start with n (since indices only go to n-1)
    for i in range(n):
        result ^= i ^ nums[i]
    return result


def single_non_duplicate(nums: list[int]) -> int:
    """
    LeetCode #540: Single element in sorted array
    All elements appear twice except one
    
    Binary search exploiting sorted property (more efficient than raw XOR):
    Before the single element, pairs start at even indices
    After it, pairs start at odd indices
    """
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if mid % 2 == 1:
            mid -= 1
        if nums[mid] == nums[mid + 1]:
            lo = mid + 2
        else:
            hi = mid
    return nums[lo]


def find_complement(n: int) -> int:
    """
    LeetCode #476: Number Complement
    Flip all significant bits (excluding leading zeros)
    
    Example: 5 = 101, complement = 010 = 2
    """
    mask = 1
    while mask <= n:
        mask <<= 1
    mask -= 1  # e.g., n=5(101), mask = 111 = 7
    
    return n ^ mask


# Tests
print(f"reverse_bits(43261596) = {reverse_bits(43261596)}")
print(f"missing_number([3,0,1]) = {missing_number([3, 0, 1])}")  # 2
print(f"single_non_duplicate([1,1,2,3,3,4,4,8,8]) = {single_non_duplicate([1,1,2,3,3,4,4,8,8])}")  # 2
print(f"complement(5) = {find_complement(5)}")  # 2

4.7 Real-World Engineering Applications of Bit Operations

1. Bit operations in network protocols

def parse_ipv4(ip_int: int) -> str:
    """Parse 32-bit integer as IPv4 address"""
    return f"{(ip_int >> 24) & 0xFF}.{(ip_int >> 16) & 0xFF}.{(ip_int >> 8) & 0xFF}.{ip_int & 0xFF}"

def ip_to_int(ip: str) -> int:
    """Convert IPv4 address to 32-bit integer"""
    parts = [int(p) for p in ip.split('.')]
    return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3]

def subnet_match(ip: str, subnet: str) -> bool:
    """
    Check if IP is in subnet
    Subnet format: 192.168.1.0/24
    
    Method: compare first prefix_len bits of IP and network address
    """
    network, prefix_len = subnet.split('/')
    prefix_len = int(prefix_len)
    
    ip_int = ip_to_int(ip)
    network_int = ip_to_int(network)
    
    # Mask: first prefix_len bits are 1, rest are 0
    mask = (0xFFFFFFFF << (32 - prefix_len)) & 0xFFFFFFFF
    
    return (ip_int & mask) == (network_int & mask)


# Demo
print(parse_ipv4(0xC0A80101))  # 192.168.1.1
print(f"192.168.1.100 in 192.168.1.0/24: {subnet_match('192.168.1.100', '192.168.1.0/24')}")  # True
print(f"192.168.2.1 in 192.168.1.0/24: {subnet_match('192.168.2.1', '192.168.1.0/24')}")      # False

2. Bit operations in hash functions

def murmur_hash_mix(h: int) -> int:
    """
    MurmurHash3 finalization mix
    Bit operations scatter hash values to reduce collisions
    """
    h ^= h >> 16
    h = (h * 0x85ebca6b) & 0xFFFFFFFF
    h ^= h >> 13
    h = (h * 0xc2b2ae35) & 0xFFFFFFFF
    h ^= h >> 16
    return h


def fibonacci_hash(key: int, bits: int = 10) -> int:
    """
    Fibonacci hashing (for HashMap slot indexing)
    
    Uses bit-operation approximation of golden ratio: 2^32 / phi ~ 2654435769
    Multiply by this magic number and take high bits for very uniform distribution
    
    This is the hashing method used by Java HashMap and Linux kernel
    """
    GOLDEN_RATIO = 2654435769  # 2^32 * (sqrt(5) - 1) / 2
    return ((key * GOLDEN_RATIO) & 0xFFFFFFFF) >> (32 - bits)

3. Bit operations in game development

# Collision Layers use bitmasks
LAYER_PLAYER = 1 << 0     # 0001
LAYER_ENEMY = 1 << 1      # 0010
LAYER_BULLET = 1 << 2     # 0100
LAYER_WALL = 1 << 3       # 1000

# Define which layers each object can collide with
player_collision_mask = LAYER_ENEMY | LAYER_WALL      # 1010
bullet_collision_mask = LAYER_ENEMY | LAYER_WALL      # 1010
enemy_collision_mask = LAYER_PLAYER | LAYER_BULLET    # 0101

def can_collide(obj_layer: int, target_mask: int) -> bool:
    """Check if two objects can collide"""
    return bool(obj_layer & target_mask)

print(f"Bullet hits enemy: {can_collide(LAYER_BULLET, enemy_collision_mask)}")  # True
print(f"Bullet hits player: {can_collide(LAYER_BULLET, player_collision_mask)}")  # False

4.8 Chapter Summary

Bit manipulation is where algorithms meet hardware. In interviews, it tests your understanding of binary representation; in engineering, it helps you write high-performance code; in systems design, it's the foundational language of network protocols, cryptography, and operating systems.

Remember one core principle: Computers don't understand "numbers" — they only understand bits. When you think in bit operations, you're programming in the computer's native language.