Bit Manipulation Mastery

Bit manipulation is the secret weapon of systems programmers and computer architects. These techniques appear everywhere - from hash functions to graphics algorithms to hardware design. Let's master the art of thinking in binary! 🔢

1. Quick Reference Arsenal

Your go-to toolkit for any bit manipulation challenge:

// Test k-th bit
if (x & (1u << k))
 
// Set / clear / toggle k-th bit  
x |= (1u << k)      // set
x &= ~(1u << k)     // clear
x ^= (1u << k)      // toggle
 
// Isolate lowest set bit
lsb = x & -x
 
// Clear lowest set bit
x &= (x - 1)
 
// Count set bits (Kernighan's algorithm)
while (x) { x &= x - 1; ++cnt; }
 
// Power of two test (x > 0)
(x & (x - 1)) == 0
 
// Multiply/divide by 2^k
x << k    // multiply
x >> k    // divide (mind sign extension)

2. Classic Problem Patterns

2.1 1. Single Number (XOR Cancellation)

Problem: Every element appears twice except one. Find the unique element.

Key insight: XOR has magical properties - x ^ x = 0 and 0 ^ y = y

int singleNumber(const vector<int>& nums) {
    int result = 0;
    for (int x : nums) {
        result ^= x;  // Pairs cancel out
    }
    return result;
}

Why it works:

XOR is associative and commutative
Duplicate pairs: a ^ a = 0
Final result: 0 ^ unique = unique

2.2 2. Two Unique Numbers (XOR Split)

Problem: Every element appears twice except two. Find both unique elements.

Strategy: Use XOR to find diff = a ^ b, then split array based on any set bit in diff.

pair<int,int> twoSingles(const vector<int>& nums) {
    // Step 1: XOR all numbers to get a ^ b
    int xor_all = 0;
    for (int x : nums) xor_all ^= x;
    
    // Step 2: Find any bit where a and b differ
    int diff_bit = xor_all & -xor_all;  // Isolate rightmost set bit
    
    // Step 3: Split array into two groups and XOR each group
    int a = 0, b = 0;
    for (int x : nums) {
        if (x & diff_bit) {
            a ^= x;  // Group 1: bit is set
        } else {
            b ^= x;  // Group 2: bit is clear
        }
    }
    
    return {a, b};
}

Key insight: If a ^ b has a bit set at position k, then a and b have different values at position k. This lets us partition the array!

2.3 3. Single Number (K Occurrences)

Problem: Every element appears k times except one. Find the unique element.

Strategy: Count bits at each position modulo k.

int singleNumberK(const vector<int>& nums, int k = 3) {
    int result = 0;
    
    // Process each bit position
    for (int bit = 0; bit < 32; bit++) {
        int count = 0;
        
        // Count how many numbers have this bit set
        for (int x : nums) {
            count += (x >> bit) & 1;
        }
        
        // If count % k != 0, the unique number has this bit set
        if (count % k != 0) {
            result |= (1 << bit);
        }
    }
    
    return result;
}

Complexity: O(32n) = O(n), works for any k

3. Missing Number Techniques

3.1 4. Find Missing Number in [0..n]

Problem: Given n numbers from range [0..n], find the missing one.

XOR approach (elegant and overflow-safe):

int missingNumber(const vector<int>& nums) {
    int n = nums.size();
    int result = 0;
    
    // XOR all numbers from 0 to n
    for (int i = 0; i <= n; i++) {
        result ^= i;
    }
    
    // XOR all numbers in array
    for (int x : nums) {
        result ^= x;
    }
    
    return result;  // Missing number remains
}

Alternative approaches:

// Sum formula (watch for overflow)
int expected_sum = n * (n + 1) / 2;
int actual_sum = accumulate(nums.begin(), nums.end(), 0);
return expected_sum - actual_sum;
 
// Bit manipulation with index pairing
int result = nums.size();
for (int i = 0; i < nums.size(); i++) {
    result ^= i ^ nums[i];
}
return result;

3.2 5. Two Missing Numbers

Problem: Given n-2 numbers from range [1..n], find both missing numbers.

Strategy: Combine XOR split technique with range [1..n].

pair<int,int> twoMissing(const vector<int>& nums, int n) {
    // XOR all numbers in range [1..n]
    int xor_range = 0;
    for (int i = 1; i <= n; i++) xor_range ^= i;
    
    // XOR all numbers in array
    int xor_array = 0;
    for (int x : nums) xor_array ^= x;
    
    // XOR of two missing numbers
    int xor_missing = xor_range ^ xor_array;
    
    // Split using rightmost set bit
    int diff_bit = xor_missing & -xor_missing;
    
    int missing1 = 0, missing2 = 0;
    
    // Split range [1..n]
    for (int i = 1; i <= n; i++) {
        if (i & diff_bit) missing1 ^= i;
        else missing2 ^= i;
    }
    
    // Split array elements
    for (int x : nums) {
        if (x & diff_bit) missing1 ^= x;
        else missing2 ^= x;
    }
    
    return {missing1, missing2};
}

4. Bit Counting Mastery

4.1 6. Population Count (Hamming Weight)

Brian Kernighan's Algorithm - elegant and efficient:

int popcount(unsigned x) {
    int count = 0;
    while (x) {
        x &= x - 1;  // Clear lowest set bit
        count++;
    }
    return count;
}

Why x & (x-1) clears the lowest set bit:

If x = ...abc1000 (rightmost 1 followed by zeros)
Then x-1 = ...abc0111 (borrow propagates)
So x & (x-1) = ...abc0000 (clears the rightmost 1)

Built-in alternatives:

int count = __builtin_popcount(x);        // 32-bit
int count = __builtin_popcountll(x);      // 64-bit
 
// C++20 standard library
#include <bit>
int count = std::popcount(x);

4.2 7. Parity Computation

Problem: Determine if number has even or odd number of 1-bits.

Parallel reduction approach:

int parity(unsigned x) {
    x ^= x >> 16;  // Fold upper 16 bits into lower 16
    x ^= x >> 8;   // Fold upper 8 bits into lower 8
    x ^= x >> 4;   // Fold upper 4 bits into lower 4
    x &= 0xF;      // Keep only lower 4 bits
    
    // Lookup table for 4-bit parity
    static const int parity_table[16] = {
        0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
    };
    
    return parity_table[x];
}

Key insight: XOR is associative, so we can fold the computation tree-style.

5. Bit Reversal & Rotation

5.1 8. Reverse Bits (32-bit)

Parallel bit reversal using divide-and-conquer:

uint32_t reverseBits(uint32_t x) {
    // Swap adjacent bits
    x = (x >> 1)  & 0x55555555u | (x & 0x55555555u) << 1;
    
    // Swap adjacent 2-bit groups  
    x = (x >> 2)  & 0x33333333u | (x & 0x33333333u) << 2;
    
    // Swap adjacent 4-bit groups
    x = (x >> 4)  & 0x0F0F0F0Fu | (x & 0x0F0F0F0Fu) << 4;
    
    // Swap adjacent 8-bit groups
    x = (x >> 8)  & 0x00FF00FFu | (x & 0x00FF00FFu) << 8;
    
    // Swap 16-bit halves
    x = (x >> 16)               | (x               ) << 16;
    
    return x;
}

Magic constants explained:

0x55555555 = 01010101... (alternating bits)
0x33333333 = 00110011... (alternating 2-bit groups)
0x0F0F0F0F = 00001111... (alternating 4-bit groups)

6. Advanced Subset Techniques

6.1 9. Subset Enumeration

All subsets of n elements:

void enumerateAllSubsets(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        cout << "Subset: ";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                cout << i << " ";
            }
        }
        cout << endl;
    }
}

All submasks of a given mask (classic DP trick):

void enumerateSubmasks(int mask) {
    // Iterate through all non-empty submasks
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        // Process submask
        cout << "Submask: " << bitset<8>(submask) << endl;
    }
    
    // Don't forget the empty submask (0) if needed
}

How submask iteration works:

submask - 1 flips all trailing zeros and the rightmost 1
& mask keeps only bits that were set in original mask
This generates all submasks in decreasing order

6.2 10. Bitmask Dynamic Programming

Traveling Salesman Problem pattern:

// dp[mask][i] = minimum cost to visit cities in 'mask', ending at city 'i'
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
 
// Base case: start at city 0
dp[1][0] = 0;
 
// Fill DP table
for (int mask = 1; mask < (1 << n); mask++) {
    for (int u = 0; u < n; u++) {
        if (!(mask & (1 << u))) continue;  // u not in current subset
        
        // Try all previous cities
        int prev_mask = mask ^ (1 << u);  // Remove u from mask
        for (int v = 0; v < n; v++) {
            if (prev_mask & (1 << v)) {
                dp[mask][u] = min(dp[mask][u], dp[prev_mask][v] + dist[v][u]);
            }
        }
    }
}

7. Low-Level Bit Tricks

7.1 11. Isolate & Clear Lowest Set Bit

// Isolate lowest set bit
unsigned lsb = x & -x;
// Also works: x & (~x + 1)
 
// Clear lowest set bit  
x &= x - 1;
 
// Practical use: iterate through set bits
while (x) {
    int bit_pos = __builtin_ctz(x);  // Count trailing zeros
    // Process bit at position bit_pos
    x &= x - 1;  // Clear this bit and continue
}

Two's complement magic: -x = ~x + 1, so x & -x isolates the rightmost 1-bit.

7.2 12. XOR Swap (Interview Candy)

void xorSwap(int& a, int& b) {
    if (&a == &b) return;  // Guard against self-swap!
    
    a ^= b;
    b ^= a;  // b = b ^ (a ^ b) = a
    a ^= b;  // a = (a ^ b) ^ a = b
}

Note: In production code, use std::swap(). This is just for interviews!

7.3 13. Power of Two Detection

bool isPowerOfTwo(unsigned x) {
    return x && !(x & (x - 1));
}
 
// Why this works:
// Power of 2: exactly one bit set (e.g., 1000)
// x - 1: flips all bits after and including the set bit (0111)
// x & (x - 1): result is 0 only for powers of 2

8. Gray Code & Advanced Patterns

8.1 14. Gray Code Generation

Binary to Gray conversion:

unsigned binaryToGray(unsigned n) {
    return n ^ (n >> 1);
}

Gray to Binary conversion:

unsigned grayToBinary(unsigned g) {
    for (unsigned shift = 1; shift < 32; shift <<= 1) {
        g ^= g >> shift;
    }
    return g;
}

Property: Adjacent Gray codes differ by exactly one bit - useful for minimizing switching in hardware.

8.2 15. Fast Set Operations (Small Universe)

For sets with elements in range [0, 63], use uint64_t as bitset:

class FastSet {
    uint64_t bits = 0;
    
public:
    void insert(int x) { bits |= 1ULL << x; }
    void erase(int x) { bits &= ~(1ULL << x); }
    bool contains(int x) const { return (bits >> x) & 1ULL; }
    int size() const { return __builtin_popcountll(bits); }
    
    // Set operations
    FastSet operator|(const FastSet& other) const {
        FastSet result;
        result.bits = bits | other.bits;
        return result;
    }
    
    FastSet operator&(const FastSet& other) const {
        FastSet result;
        result.bits = bits & other.bits;
        return result;
    }
};

9. Interview Problem Patterns

Quick Check

What does the expression `x & -x` compute?

Quick Check

Which technique efficiently counts set bits in a number?

10. Practice Problem Categories

10.1 XOR-Based Problems

Single Number: Use XOR cancellation property
Two Single Numbers: XOR all, then split on any differing bit
Missing Number: XOR with expected range
Array Transformation: XOR for in-place swaps

10.2 Bit Counting & Manipulation

Hamming Weight: Brian Kernighan's or built-in popcount
Parity: Parallel reduction with XOR
Bit Reversal: Divide-and-conquer with magic constants
Power of Two: x && !(x & (x-1))

10.3 Subset Enumeration

All Subsets: Iterate 0 to (1<<n)-1
All Submasks: Use submask = (submask-1) & mask trick
Bitmask DP: TSP, assignment problems, subset sum

10.4 Low-Level Optimizations

Fast Set Operations: Use bitsets for small universes
Bit Parallel Algorithms: SWAR (SIMD Within A Register)
Hardware Intrinsics: __builtin_* functions

11. Interview Talk-Track Template

When explaining bit manipulation solutions:

Anchor (1 line): State the key insight
- "I'll use XOR because duplicates cancel (x ^ x = 0)"
Expand (2-3 bullets):
- "XOR is associative and commutative, so order doesn't matter"
- "One pass, O(n) time, O(1) space - no sorting needed"
Close (result/edge cases):
- "Works for any integer range, including negatives due to two's complement"

12. Key Takeaways

XOR is magical: Master the cancellation property for uniqueness problems
Brian Kernighan's algorithm: x &= x-1 clears the lowest set bit
Two's complement arithmetic: -x = ~x + 1 enables x & -x trick
Subset iteration: Use bitmasks for exponential algorithms
Built-in functions: Know __builtin_popcount and friends
Bit parallel techniques: Think SIMD within a register for performance

Bit manipulation is about seeing patterns in binary. Once you recognize the common tricks, these problems become elegant one-liners! 🎯

Prerequisites

Learning Objectives

Table of Contents

Bit Manipulation Mastery

1. Quick Reference Arsenal

2. Classic Problem Patterns

2.1 1. Single Number (XOR Cancellation)

2.2 2. Two Unique Numbers (XOR Split)

2.3 3. Single Number (K Occurrences)

3. Missing Number Techniques

3.1 4. Find Missing Number in [0..n]

3.2 5. Two Missing Numbers

4. Bit Counting Mastery

4.1 6. Population Count (Hamming Weight)

4.2 7. Parity Computation

5. Bit Reversal & Rotation

5.1 8. Reverse Bits (32-bit)

6. Advanced Subset Techniques

6.1 9. Subset Enumeration

6.2 10. Bitmask Dynamic Programming

7. Low-Level Bit Tricks

7.1 11. Isolate & Clear Lowest Set Bit

7.2 12. XOR Swap (Interview Candy)

7.3 13. Power of Two Detection

8. Gray Code & Advanced Patterns

8.1 14. Gray Code Generation

8.2 15. Fast Set Operations (Small Universe)

9. Interview Problem Patterns

Quick Check

Quick Check

10. Practice Problem Categories

10.1 XOR-Based Problems

10.2 Bit Counting & Manipulation

10.3 Subset Enumeration

10.4 Low-Level Optimizations

11. Interview Talk-Track Template

12. Key Takeaways

In This Topic

Related Topics

Quick Actions