Chapter 10: Bit Manipulation

1. Bitwise Operations

Common Bitwise Operations

# AND: & (both bits must be 1)
5 & 3  # 101 & 011 = 001 = 1

# OR: | (at least one bit is 1)
5 | 3  # 101 | 011 = 111 = 7

# XOR: ^ (bits differ)
5 ^ 3  # 101 ^ 011 = 110 = 6

# NOT: ~ (flip all bits)
~5     # ~101 = ...11111010 (depends on bit width)

# Left Shift: << (multiply by 2^n)
5 << 2  # 101 << 2 = 10100 = 20 (5 * 4)

# Right Shift: >> (divide by 2^n)
20 >> 2  # 10100 >> 2 = 101 = 5 (20 / 4)

2. Single Number (XOR Pattern)

Example: Find Single Number

Problem: Every number appears twice except one. Find the single number.

def single_number(nums):
    """
    Find single number using XOR.
    
    Args:
        nums: List where every number appears twice except one
    
    Returns:
        The single number
    """
    # Step 1: Initialize result
    result = 0
    
    # Step 2: XOR all numbers
    for num in nums:
        # Step 2a: XOR operation
        # XOR properties:
        # - a ^ a = 0 (same number cancels out)
        # - a ^ 0 = a (XOR with 0 returns number)
        # - XOR is commutative and associative
        result ^= num
    
    # Step 3: Return result
    # All pairs cancel out (a ^ a = 0)
    # Only single number remains
    return result

Example:

nums = [4, 1, 2, 1, 2]

4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4

3. Count Set Bits

Example: Number of 1 Bits

def count_bits(n):
    """
    Count number of set bits (1s) in binary representation.
    
    Args:
        n: Integer
    
    Returns:
        Number of set bits
    """
    count = 0
    
    # Step 1: Continue while n > 0
    while n:
        # Step 2: Check if least significant bit is 1
        # n & 1 checks if last bit is set
        if n & 1:
            count += 1
        
        # Step 3: Right shift to check next bit
        # n >>= 1 moves to next bit
        n >>= 1
    
    return count

Optimized Version (Brian Kernighan's Algorithm)

def count_bits_optimized(n):
    """
    Count set bits using Brian Kernighan's algorithm.
    
    Key insight: n & (n - 1) clears the rightmost set bit.
    """
    count = 0
    
    # Step 1: Continue while n > 0
    while n:
        # Step 2: Clear rightmost set bit
        # n & (n - 1) removes the rightmost 1
        n = n & (n - 1)
        count += 1
    
    return count

4. Power of Two

Example: Check if Number is Power of 2

def is_power_of_two(n):
    """
    Check if n is a power of 2.
    
    Args:
        n: Positive integer
    
    Returns:
        True if n is power of 2, False otherwise
    """
    # Step 1: Handle edge case
    if n <= 0:
        return False
    
    # Step 2: Power of 2 has exactly one set bit
    # n & (n - 1) clears the rightmost set bit
    # If result is 0, n had exactly one set bit
    return (n & (n - 1)) == 0

5. Missing Number

Example: Find Missing Number Using XOR

Problem: Array contains n distinct numbers in range [0, n]. One is missing. Find it.

def missing_number(nums):
    """
    Find missing number using XOR.
    
    Args:
        nums: Array of n distinct numbers in range [0, n] (one missing)
    
    Returns:
        Missing number
    """
    # Step 1: XOR all numbers in array
    result = 0
    for num in nums:
        result ^= num
    
    # Step 2: XOR with all numbers from 0 to n
    # This includes the missing number
    for i in range(len(nums) + 1):
        result ^= i
    
    # Step 3: Result is the missing number
    # All numbers appear twice (once in nums, once in range)
    # Except missing number (appears only in range)
    return result

Example:

nums = [3, 0, 1], n = 3

XOR array: 3 ^ 0 ^ 1 = 2

XOR range: 2 ^ 0 ^ 1 ^ 2 ^ 3 = 2

Missing: 2

6. Reverse Bits

Example: Reverse Bits of 32-bit Integer

def reverse_bits(n):
    """
    Reverse bits of 32-bit unsigned integer.
    
    Args:
        n: 32-bit unsigned integer
    
    Returns:
        Integer with reversed bits
    """
    result = 0
    
    # Step 1: Process all 32 bits
    for i in range(32):
        # Step 2: Extract bit at position i
        # (n >> i) & 1 gets the i-th bit
        bit = (n >> i) & 1
        
        # Step 3: Place bit at reversed position
        # Position i should go to position (31 - i)
        # Left shift to correct position and OR with result
        result |= (bit << (31 - i))
    
    # Step 4: Return reversed bits
    return result

📚 Chapter Summary

• XOR Properties: a ^ a = 0, a ^ 0 = a, commutative and associative
• Common Tricks: n & (n - 1) clears rightmost set bit, n & 1 checks if odd
• Set Bits: Count using loop or Brian Kernighan's algorithm
• Power of 2: Check if (n & (n - 1)) == 0
• Bit Manipulation: Often more efficient than arithmetic operations

Key Takeaway: Bit manipulation is powerful for optimization and set operations. XOR is particularly useful for finding unique elements. Remember common patterns like clearing rightmost bit.