bit_patterns.cpp

/*
Bit Manipulation Patterns
Mathematical Foundation: Binary representation, bitwise operations
XOR properties: a^a=0, a^0=a, commutative, associative
Applications: Single number, subset generation, power of 2 checks
*/

#include <bits/stdc++.h>
using namespace std;

// Single Number
// LeetCode: 136. Single Number
// https://leetcode.com/problems/single-number/
int singleNumber(vector<int>& a) {
    int res = 0;
    for (int x : a) res ^= x;
    return res;
}

// Single Number II
// LeetCode: 137. Single Number II
// https://leetcode.com/problems/single-number-ii/
int singleNumber2(vector<int>& a) {
    int ones = 0, twos = 0;
    for (int x : a) {
        ones = (ones ^ x) & ~twos;
        twos = (twos ^ x) & ~ones;
    }
    return ones;
}

// Number of 1 Bits
// LeetCode: 191. Number of 1 Bits
// https://leetcode.com/problems/number-of-1-bits/
int hammingWeight(uint32_t n) {
    int cnt = 0;
    while (n) {
        cnt++;
        n &= n - 1; // Remove rightmost 1 bit
    }
    return cnt;
}

// Power of Two
// LeetCode: 231. Power of Two
// https://leetcode.com/problems/power-of-two/
bool isPowerOfTwo(int n) {
    return n > 0 && (n & n - 1) == 0;
}

// Reverse Bits
// LeetCode: 190. Reverse Bits
// https://leetcode.com/problems/reverse-bits/
uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1);
        n >>= 1;
    }
    return res;
}

// Missing Number
// LeetCode: 268. Missing Number
// https://leetcode.com/problems/missing-number/
int missingNumber(vector<int>& a) {
    int res = a.size();
    for (int i = 0; i < a.size(); i++) res ^= i ^ a[i];
    return res;
}

// Find the Duplicate Number
// LeetCode: 287. Find the Duplicate Number
// https://leetcode.com/problems/find-the-duplicate-number/
int findDuplicate(vector<int>& a) {
    int slow = a[0], fast = a[0];
    do {
        slow = a[slow];
        fast = a[a[fast]];
    } while (slow != fast);
    
    slow = a[0];
    while (slow != fast) {
        slow = a[slow];
        fast = a[fast];
    }
    return slow;
}

// Subsets (Bit Manipulation)
// LeetCode: 78. Subsets
// https://leetcode.com/problems/subsets/
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    int n = nums.size();
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) subset.push_back(nums[i]);
        }
        res.push_back(subset);
    }
    return res;
}

// Maximum XOR of Two Numbers
// LeetCode: 421. Maximum XOR of Two Numbers in an Array
// https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
int findMaximumXOR(vector<int>& a) {
    int mx = 0, mask = 0;
    for (int i = 30; i >= 0; i--) {
        mask |= (1 << i);
        unordered_set<int> prefixes;
        for (int x : a) prefixes.insert(x & mask);
        
        int temp = mx | (1 << i);
        for (int prefix : prefixes) {
            if (prefixes.count(temp ^ prefix)) {
                mx = temp;
                break;
            }
        }
    }
    return mx;
}

// Sum of Two Integers (No + operator)
// LeetCode: 371. Sum of Two Integers
// https://leetcode.com/problems/sum-of-two-integers/
int getSum(int a, int b) {
    while (b) {
        int carry = (unsigned int)(a & b) << 1;
        a ^= b;
        b = carry;
    }
    return a;
}

// Counting Bits
// LeetCode: 338. Counting Bits
// https://leetcode.com/problems/counting-bits/
vector<int> countBits(int n) {
    vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

// Gray Code
// LeetCode: 89. Gray Code
// https://leetcode.com/problems/gray-code/
vector<int> grayCode(int n) {
    vector<int> res;
    for (int i = 0; i < (1 << n); i++) {
        res.push_back(i ^ (i >> 1));
    }
    return res;
}

// Bitwise AND of Numbers Range
// LeetCode: 201. Bitwise AND of Numbers Range
// https://leetcode.com/problems/bitwise-and-of-numbers-range/
int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;
}

// Minimum Flips to Make a OR b Equal to c
// LeetCode: 1318. Minimum Flips to Make a OR b Equal to c
// https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/
int minFlips(int a, int b, int c) {
    int flips = 0;
    while (a || b || c) {
        int bit_a = a & 1, bit_b = b & 1, bit_c = c & 1;
        if (bit_c == 0) {
            flips += bit_a + bit_b;
        } else {
            if (bit_a == 0 && bit_b == 0) flips++;
        }
        a >>= 1; b >>= 1; c >>= 1;
    }
    return flips;
}

// Check if bits are set in specific positions
bool checkBit(int n, int pos) { return n & (1 << pos); }
int setBit(int n, int pos) { return n | (1 << pos); }
int clearBit(int n, int pos) { return n & ~(1 << pos); }
int toggleBit(int n, int pos) { return n ^ (1 << pos); }

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

// Check if number has only one bit set
bool hasOnlyOneBit(int n) { return n > 0 && (n & (n - 1)) == 0; }

// Swap two numbers without temp variable
void swapNumbers(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}