Advanced Bit Manipulation

Advanced bit manipulation techniques for complex problems

Explore advanced bit manipulation techniques for solving complex algorithmic problems.

Single Number Problems

Single Number I

• Problem: Array where every number appears twice except one
• Solution: XOR all numbers
• Time Complexity: O(n)
• Space Complexity: O(1)

Single Number II

• Problem: Array where every number appears three times except one
• Solution: Count bits at each position, modulo 3
• Time Complexity: O(n)
• Space Complexity: O(1)

Single Number III

• Problem: Array where every number appears twice except two
• Solution: XOR to get difference, then separate groups
• Time Complexity: O(n)
• Space Complexity: O(1)

Missing Number Problems

Missing Number

• Problem: Array of n-1 numbers from 0 to n, find missing
• Solution: XOR all numbers with 0 to n
• Alternative: Sum formula n*(n+1)/2 - sum

Missing Two Numbers

• Problem: Array of n-2 numbers from 1 to n, find missing two
• Solution: Use sum and sum of squares to get equations

Power of 2 Problems

Check Power of 2

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Next Power of 2

int nextPowerOfTwo(int n) {
    if (n == 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

Previous Power of 2

int prevPowerOfTwo(int n) {
    if (n <= 1) return 0;
    return 1 << (31 - __builtin_clz(n));
}

Bit Manipulation in Arrays

Maximum XOR of Two Numbers

• Problem: Find maximum XOR of any two numbers in array
• Solution: Use Trie or bit manipulation with prefix

Subarray XOR

• Problem: Find subarray with maximum XOR
• Solution: Use prefix XOR and Trie

Count Triplets with XOR Zero

• Problem: Count triplets (i, j, k) where arr[i] ^ arr[j] ^ arr[k] = 0
• Solution: Use property that a ^ b ^ c = 0 implies a ^ b = c

Bit Manipulation in Strings

Maximum XOR of Two Strings

• Problem: Find maximum XOR of two binary strings
• Solution: Greedy approach with bit manipulation

Gray Code

• Problem: Generate n-bit Gray code sequence
• Solution: Use formula i ^ (i >> 1)

Hamming Distance

• Problem: Count positions where bits differ
• Solution: XOR and count set bits

Advanced Techniques

Bit Manipulation in Dynamic Programming

Subset Sum with Bitmask

// Check if subset sum equals target
bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2) return false;
    
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    
    for (int num : nums) {
        for (int i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

Traveling Salesman with Bitmask

// TSP using bitmask DP
int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    
    dp[1][0] = 0;  // Start at city 0
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], 
                                   dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    int result = INT_MAX;
    for (int i = 1; i < n; i++) {
        result = min(result, dp[(1 << n) - 1][i] + dist[i][0]);
    }
    return result;
}

Bit Manipulation in Graph Algorithms

Hamiltonian Path with Bitmask

// Check if Hamiltonian path exists
bool hasHamiltonianPath(vector<vector<int>>& graph) {
    int n = graph.size();
    
    for (int start = 0; start < n; start++) {
        vector<vector<bool>> dp(1 << n, vector<bool>(n, false));
        dp[1 << start][start] = true;
        
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int u = 0; u < n; u++) {
                if (!(mask & (1 << u)) || !dp[mask][u]) continue;
                
                for (int v : graph[u]) {
                    if (mask & (1 << v)) continue;
                    
                    int newMask = mask | (1 << v);
                    dp[newMask][v] = true;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (dp[(1 << n) - 1][i]) return true;
        }
    }
    return false;
}

Optimization Techniques

Fast Bit Counting

// Hamming weight using bit manipulation
int popcount(uint32_t n) {
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n + (n >> 4)) & 0x0f0f0f0f;
    n = n + (n >> 8);
    n = n + (n >> 16);
    return n & 0x3f;
}

Bit Reversal

// Reverse bits of a 32-bit integer
uint32_t reverseBits(uint32_t n) {
    n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
    n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
    return n;
}

Common Patterns

1. XOR Properties: a ^ a = 0, a ^ 0 = a, a ^ b = b ^ a
2. Bitmask Subsets: Generate all subsets using bitmasks
3. State Compression: Use bits to represent visited states
4. Prefix XOR: Use XOR prefix for range queries
5. Trie with Bits: Use Trie for bit manipulation problems

Advanced Applications and Case Studies

Subset Generation Using Bitmasks

// Generate all subsets of an array using bitmask
vector<vector<int>> generateSubsets(vector<int>& nums) {
    vector<vector<int>> result;
    int n = nums.size();

    // Iterate through all possible subsets (2^n)
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int i = 0; i < n; i++) {
            // Check if i-th bit is set
            if (mask & (1 << i)) {
                subset.push_back(nums[i]);
            }
        }
        result.push_back(subset);
    }

    return result;
}

// Example: nums = [1, 2, 3]
// Masks: 000 (empty), 001 ([1]), 010 ([2]), 011 ([1,2]), ...
// Generates all 2^3 = 8 subsets

Josephus Problem with Bit Manipulation

// Find survivor in Josephus problem (every 2nd person eliminated)
int josephus(int n) {
    // For k=2, there's a formula: J(n) = 2*L + 1
    // where n = 2^m + L, 0 <= L < 2^m

    int powerOf2 = 1;
    while (powerOf2 <= n) {
        powerOf2 <<= 1;
    }
    powerOf2 >>= 1;  // Largest power of 2 <= n

    int L = n - powerOf2;
    return 2 * L + 1;
}

// Example: n=8 → powerOf2=8, L=0 → survivor=1
// Example: n=5 → powerOf2=4, L=1 → survivor=3

Bit Manipulation in Graph Algorithms

// Bipartite Graph Detection using BFS with bit coloring
bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    int* color = new int[n];
    memset(color, -1, sizeof(int) * n);

    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            queue<int> q;
            q.push(i);
            color[i] = 0;  // Color 0 (represented as bit)

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (int v : graph[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];  // Alternate color
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;  // Not bipartite
                    }
                }
            }
        }
    }

    return true;
}

Bloom Filters for Membership Testing

class BloomFilter {
    static const int SIZE = 1000000;
    bitset<SIZE> bits;

public:
    // Hash functions
    int hash1(const string& s) {
        return hash<string>{}(s) % SIZE;
    }

    int hash2(const string& s) {
        return (hash<string>{}(s) * 31) % SIZE;
    }

    int hash3(const string& s) {
        return (hash<string>{}(s) * 97) % SIZE;
    }

    void insert(const string& s) {
        bits[hash1(s)] = 1;
        bits[hash2(s)] = 1;
        bits[hash3(s)] = 1;
    }

    bool contains(const string& s) {
        return bits[hash1(s)] && bits[hash2(s)] && bits[hash3(s)];
    }
};

// Space-efficient: 1M bits = 125KB for ~100K items with 1% false positive rate
// Much better than storing all strings

Bit Manipulation for State Compression

// Compress game state using bits
class ChessState {
    // 64 squares * 12 piece types = 768 bits (96 bytes)
    // Using bits: can represent in 8 uint64_t values
    uint64_t position[12];  // 12 piece types

public:
    // Place piece at position
    void placePiece(int pieceType, int square) {
        position[pieceType] |= (1ULL << square);
    }

    // Check if square occupied
    bool isOccupied(int square) {
        for (int i = 0; i < 12; i++) {
            if (position[i] & (1ULL << square)) {
                return true;
            }
        }
        return false;
    }

    // Get piece type at square
    int getPieceType(int square) {
        for (int i = 0; i < 12; i++) {
            if (position[i] & (1ULL << square)) {
                return i;
            }
        }
        return -1;
    }
};

// Efficient: entire chess board = 96 bytes (vs 512+ bytes for array representation)

Performance Comparison: XOR Swap vs Traditional

// Bit manipulation XOR swap (no temporary variable)
void xorSwap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
    // After: a and b are swapped
}

// Performance:
// - Modern CPUs: XOR swap is SLOWER (more instructions, harder to pipeline)
// - Use temporary swap or std::swap instead
// - Compiler optimizations handle this better

// Right approach:
void properSwap(int& a, int& b) {
    swap(a, b);  // Let compiler optimize
}

Bit Manipulation Interview Problems

Problem: Find All Single Numbers (appeared 3 times except one)

int singleNumber(vector<int>& nums) {
    int ones = 0, twos = 0;

    for (int num : nums) {
        twos |= ones & num;
        ones ^= num;

        int threes = ones & twos;
        ones &= ~threes;
        twos &= ~threes;
    }

    return ones;
}

// Time: O(n), Space: O(1)
// Idea: Track which bits appeared 1 time vs 2 times vs 3 times

Problem: Majority Element (appeared more than n/3 times)

vector<int> majorityElement(vector<int>& nums) {
    int num1 = 0, num2 = 0, count1 = 0, count2 = 0;

    for (int num : nums) {
        if (num == num1) {
            count1++;
        } else if (num == num2) {
            count2++;
        } else if (count1 == 0) {
            num1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            num2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    // Verify candidates
    vector<int> result;
    count1 = count2 = 0;
    for (int num : nums) {
        if (num == num1) count1++;
        else if (num == num2) count2++;
    }

    if (count1 > nums.size() / 3) result.push_back(num1);
    if (count2 > nums.size() / 3) result.push_back(num2);

    return result;
}

// Time: O(n), Space: O(1)
// Boyer-Moore majority vote variant

Performance Considerations

• Use built-in functions when available (__builtin_popcount, __builtin_clz)

  • __builtin_popcount: Count set bits (hardware instruction on modern CPUs)
  • __builtin_clz: Count leading zeros
  • __builtin_ctz: Count trailing zeros

• Prefer bitwise operations over arithmetic when possible

  • x * 2 → x << 1 (shift is faster)
  • x / 2 → x >> 1
  • x % 2 → x & 1

• Consider cache efficiency when using large bitmasks

  • Bitmasks in L1 cache: 64KB / 8 bytes = 8M bits max
  • Use contiguous arrays, not sparse matrices

• Use appropriate data types (uint32_t, uint64_t) for bit operations

  • int is platform-dependent (16/32/64 bits)
  • Use fixed-width types for portability

• Benchmark before optimizing

  • Modern compilers optimize better than hand-optimized bit code
  • Measure real impact, don't assume

Common Bit Manipulation Tricks

// Check if power of 2
bool isPowerOf2(int n) { return n > 0 && (n & (n - 1)) == 0; }

// Get rightmost set bit
int getRightmost(int n) { return n & (-n); }

// Clear rightmost set bit
int clearRightmost(int n) { return n & (n - 1); }

// Check if bit i is set
bool isBitSet(int n, int i) { return (n >> i) & 1; }

// Set bit i
int setBit(int n, int i) { return n | (1 << i); }

// Clear bit i
int clearBit(int n, int i) { return n & ~(1 << i); }

// Toggle bit i
int toggleBit(int n, int i) { return n ^ (1 << i); }

// Get all bits set up to position i
int getMask(int i) { return (1 << i) - 1; }

// Check if all bits are set
bool allSet(int n) { return n != 0 && (n & (n + 1)) == 0; }

// Reverse bits
uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}