Common Bit Manipulation Tricks

Beyond basic operations, bit manipulation has powerful tricks for solving specific problems efficiently. These patterns appear in interviews, competitive programming, and low-level systems code.

Subsets with Bitmasks

Use bits to represent set membership. For a set of n elements, iterate through all 2^n subsets:

fn generate_subsets(arr: &[i32]) -> Vec<Vec<i32>> {
    let n = arr.len();
    let mut subsets = Vec::new();

    for mask in 0..(1 << n) {  // 0 to 2^n - 1
        let mut subset = Vec::new();
        for i in 0..n {
            if (mask & (1 << i)) != 0 {  // Check if bit i is set
                subset.push(arr[i]);
            }
        }
        subsets.push(subset);
    }

    subsets
}

fn main() {
    println!("{:?}", generate_subsets(&[1, 2, 3]));
    // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
}

For [1, 2, 3]:
mask = 0: 000 → []
mask = 1: 001 → [1]
mask = 2: 010 → [2]
mask = 3: 011 → [1, 2]
mask = 4: 100 → [3]
mask = 5: 101 → [1, 3]
mask = 6: 110 → [2, 3]
mask = 7: 111 → [1, 2, 3]

Iterate Through Set Bits

Efficiently iterate only through set bits:

def iterate_set_bits(n):
    bits = []
    while n:
        lowest_bit = n & (-n)  # Isolate lowest set bit
        bits.append(lowest_bit)
        n &= (n - 1)  # Clear lowest set bit
    return bits

print(iterate_set_bits(0b10110))  # [2, 4, 16]

Two Unique Numbers

Find two numbers that appear once (others appear twice):

fn two_unique(nums: &[i32]) -> (i32, i32) {
    // XOR all numbers
    let mut xor_all = 0;
    for &num in nums {
        xor_all ^= num;
    }

    // xor_all = a ^ b where a, b are the unique numbers
    // Find any set bit (they differ at this bit)
    let diff_bit = xor_all & (-xor_all);

    // Separate into two groups
    let (mut a, mut b) = (0, 0);
    for &num in nums {
        if (num & diff_bit) != 0 {
            a ^= num;
        } else {
            b ^= num;
        }
    }

    (a, b)
}

fn main() {
    println!("{:?}", two_unique(&[1, 2, 1, 3, 2, 5]));  // (3, 5) or (5, 3)
}

Missing Number

Find the missing number in [0, n]:

fn missing_number(nums: &[i32]) -> i32 {
    let n = nums.len() as i32;
    let mut expected_xor = 0;
    let mut actual_xor = 0;

    for i in 0..=n {
        expected_xor ^= i;
    }

    for &num in nums {
        actual_xor ^= num;
    }

    expected_xor ^ actual_xor
}

// Simpler: XOR indices with values
fn missing_number_v2(nums: &[i32]) -> i32 {
    let mut result = nums.len() as i32;
    for (i, &num) in nums.iter().enumerate() {
        result ^= (i as i32) ^ num;
    }
    result
}

fn main() {
    println!("{}", missing_number(&[3, 0, 1]));  // 2
}

Counting Bits for All Numbers

Count bits for every number from 0 to n:

fn count_bits_all(n: usize) -> Vec<i32> {
    let mut dp = vec![0; n + 1];

    for i in 1..=n {
        // dp[i] = dp[i >> 1] + (i & 1)
        // Number of bits = bits in i/2 + last bit
        dp[i] = dp[i >> 1] + ((i & 1) as i32);
    }

    dp
}

fn main() {
    println!("{:?}", count_bits_all(5));  // [0, 1, 1, 2, 1, 2]
}

Single Number III (Three Times)

Find the number appearing once (others appear three times):

def single_number_three(nums):
    # Count bits at each position
    result = 0

    for i in range(32):
        bit_sum = 0
        for num in nums:
            bit_sum += (num >> i) & 1

        # If bit_sum % 3 != 0, the single number has this bit
        if bit_sum % 3:
            result |= (1 << i)

    # Handle negative numbers in Python
    if result >= 2**31:
        result -= 2**32

    return result

print(single_number_three([2, 2, 3, 2]))  # 3

Gray Code

Generate n-bit Gray code (adjacent values differ by one bit):

def gray_code(n):
    result = []
    for i in range(1 << n):
        result.append(i ^ (i >> 1))
    return result

print(gray_code(3))
# [0, 1, 3, 2, 6, 7, 5, 4]
# Binary: 000, 001, 011, 010, 110, 111, 101, 100

Add Without +

Add two integers using only bit operations:

def add(a, b):
    # Handle negative numbers with mask
    mask = 0xFFFFFFFF

    while b != 0:
        carry = (a & b) << 1
        a = (a ^ b) & mask
        b = carry & mask

    # Convert back from unsigned to signed
    if a > 0x7FFFFFFF:
        a = ~(a ^ mask)

    return a

print(add(15, 12))  # 27

15 + 12:
  1111 (15)
  1100 (12)

Step 1:
  XOR: 0011 (sum without carry)
  AND<<1: 11000 (carry)

Step 2:
  XOR: 11011 (27)
  AND<<1: 00000 (no carry)

Result: 27

Bit Manipulation in DP (Traveling Salesman)

Use bitmask to represent visited cities:

def tsp(dist):
    """Traveling Salesman using bitmask DP."""
    n = len(dist)
    INF = float('inf')

    # dp[mask][i] = min cost to visit cities in mask, ending at i
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start at city 0

    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)):
                continue
            if dp[mask][u] == INF:
                continue

            for v in range(n):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v],
                                      dp[mask][u] + dist[u][v])

    # Return to start
    full_mask = (1 << n) - 1
    return min(dp[full_mask][i] + dist[i][0] for i in range(n))

Common Interview Tricks

| Problem | Trick | |---------|-------| | Find single number | XOR all numbers | | Find missing number | XOR expected with actual | | Power of 2 | n & (n-1) == 0 | | Swap without temp | a ^= b; b ^= a; a ^= b | | Generate subsets | Iterate 0 to 2^n - 1 | | Count set bits | n &= (n-1) loop | | Get lowest set bit | n & (-n) |

Bit Manipulation for Flags

# Define flags
READ = 0b001
WRITE = 0b010
EXECUTE = 0b100

# Set permissions
permissions = 0
permissions |= READ | WRITE  # permissions = 0b011

# Check permission
has_read = permissions & READ  # True
has_execute = permissions & EXECUTE  # False

# Remove permission
permissions &= ~WRITE  # permissions = 0b001

Key Takeaways

1. Bitmasks represent subsets: iterate 0 to 2^n - 1
2. XOR finds unique elements (pairs cancel out)
3. n & (n-1) clears lowest bit, useful for counting
4. Gray code: i ^ (i >> 1)
5. Bit DP reduces state space for subset problems
6. Flags use OR to combine, AND to check, AND NOT to clear

Bit manipulation tricks are elegant and efficient. They appear in low-level systems, competitive programming, and tricky interview problems. Master these patterns, and you'll recognize when bit manipulation can simplify a solution.