Skip to main content

Advanced Bit Manipulation

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

Performance Considerations​

  • Use built-in functions when available (__builtin_popcount, __builtin_clz)
  • Prefer bitwise operations over arithmetic when possible
  • Consider cache efficiency when using large bitmasks
  • Use appropriate data types (uint32_t, uint64_t) for bit operations