Bit Manipulation

// -n = ~n + 1  (negation via bit flip + 1)
// ~n = -n - 1  (bitwise NOT of n)
// -1 = ~0      (all bits set)
 
int n = 13;
cout << (~n + 1);   // -13  ← negate using complement
cout << ~(-1);      // 0    ← NOT of all-ones = all-zeros
cout << (n & -n);   // 1    ← isolate lowest set bit: 1101 & 0011 = 0001
 
// Signed right shift (>>) fills with sign bit (arithmetic shift)
int neg = -8;       // 11111000
cout << (neg >> 1); // -4 = 11111100 (fills with 1 because negative)
 
// Use unsigned right shift via cast when needed:
unsigned int u = (unsigned int)neg >> 1;  // Fills with 0

int a = 0b1010;   // 10 in decimal
int b = 0b1100;   // 12 in decimal
 
// AND: both bits must be 1
int andResult = a & b;    // 0b1000 = 8
// Use for: masking, clearing bits, checking bit state
 
// OR: at least one bit must be 1
int orResult  = a | b;    // 0b1110 = 14
// Use for: setting bits, combining flags
 
// XOR: bits must differ (exclusive or)
int xorResult = a ^ b;    // 0b0110 = 6
// Use for: toggling bits, detecting differences, encryption
 
// NOT: flip all bits (unary)
int notResult = ~a;        // 0b...11110101 = -11 (two's complement)
// Use for: creating masks, complement operations
 
// Left Shift: multiply by 2^k (fills with 0 on right)
int lshift = a << 2;      // 0b101000 = 40 = 10 × 4
// Use for: fast multiplication by powers of 2, building masks
 
// Right Shift: divide by 2^k (arithmetic: fills with sign bit)
int rshift = a >> 1;      // 0b0101 = 5 = 10 / 2
// Use for: fast division by powers of 2, extracting upper bits

// Build a mask with bit k set:
int mask = 1 << k;           // 32-bit: only works for k < 32
long long lmask = 1LL << k;  // 64-bit: use for k up to 63
 
// Check if k-th bit is set:
bool isSet = (n >> k) & 1;   // Shift k out, check the last bit
bool isSet2 = (n & (1 << k)) != 0;  // Also valid
 
// Signed overflow warning:
// 1 << 31 is UNDEFINED BEHAVIOR in C++ for signed int!
// Use 1u << 31 or 1LL << 31 instead

// ─── SINGLE BIT OPERATIONS ──────────────────────────────
int n = 0b10110100;
int k = 2;           // Target bit position (0-indexed from right)
 
// CHECK if bit k is set → returns 0 or 1
int bit = (n >> k) & 1;                    // 1 if set, 0 if not
 
// SET bit k to 1 (regardless of current value)
int set = n | (1 << k);                    // 0b10110100 | 0b00000100 = 0b10110100
 
// CLEAR bit k to 0
int clear = n & ~(1 << k);                 // n & 0b...11111011
 
// TOGGLE bit k (0→1, 1→0)
int toggle = n ^ (1 << k);                 // XOR flips the bit
 
// ─── LOWEST SET BIT (LSB) ───────────────────────────────
int lsb = n & (-n);                        // Isolate lowest set bit
// e.g., 0b10110100 → 0b00000100 (bit 2)
// Why: -n flips all bits and adds 1, canceling all but LSB
 
int clearLSB = n & (n - 1);               // Clear the lowest set bit
// e.g., 0b10110100 → 0b10110000 (clears bit 2)
 
// ─── HIGHEST SET BIT (MSB) ──────────────────────────────
int pos = 31 - __builtin_clz(n);          // Position of MSB (n > 0)
// __builtin_clz: count leading zeros (undefined for n=0)
 
// ─── RANGE OPERATIONS ───────────────────────────────────
// Create mask of k ones: (1 << k) - 1 = 0b00...0111...1 (k ones)
int mask = (1 << k) - 1;                  // k=3 → 0b111
 
// Extract bits [lo, hi]:
int bits = (n >> lo) & ((1 << (hi-lo+1)) - 1);
 
// ─── BUILT-IN FUNCTIONS ─────────────────────────────────
__builtin_popcount(n)     // Count set bits (32-bit)
__builtin_popcountll(n)   // Count set bits (64-bit)
__builtin_ctz(n)          // Count trailing zeros (position of LSB)
__builtin_clz(n)          // Count leading zeros (0-indexed from MSB)
__builtin_parity(n)       // Parity: 1 if odd number of set bits, 0 if even

// Swap a and b without a temporary variable
// Note: FAILS if a and b are the same variable/location!
void xorSwap(int& a, int& b) {
    if (&a == &b) return;  // Guard: same address would zero both out
    a ^= b;
    b ^= a;
    a ^= b;
}
// a=5, b=3:
// a = 5^3 = 6 (0110)
// b = 3^6 = 5 (original a)
// a = 6^5 = 3 (original b)

// All numbers appear twice EXCEPT one. XOR all → pairs cancel → survivor remains.
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}
// a^a = 0, 0^b = b → all pairs cancel, single number survives
// Time: O(n), Space: O(1)

int missingNumber(vector<int>& nums) {
    int n = nums.size(), result = n;  // Start XOR with n
    for (int i = 0; i < n; i++) result ^= i ^ nums[i];
    return result;
    // XOR indices [0..n] with elements: every pair cancels, missing survives
}
// Alternative: result = n*(n+1)/2 - sum(nums)

// All numbers appear twice EXCEPT two: a and b.
vector<int> singleNumber(vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;   // xorAll = a ^ b
 
    // Find any set bit in a^b — it differs between a and b
    // Use lowest set bit to split nums into two groups
    int diffBit = xorAll & (-xorAll);  // Isolate lowest differing bit
 
    int groupA = 0, groupB = 0;
    for (int x : nums) {
        if (x & diffBit) groupA ^= x;  // Group 1: bit is set
        else             groupB ^= x;  // Group 2: bit is not set
    }
    return {groupA, groupB};
    // Each group contains one of {a, b} plus pairs (which cancel)
}
// Time: O(n), Space: O(1)

// Find the single changed bit between two values:
int changed = a ^ b;          // Set bits = positions where a and b differ
// Count differences:
int numDiff = __builtin_popcount(a ^ b);   // Hamming distance
 
// XOR as "difference detector" for arrays:
// If XOR of subarray [l..r] == 0, all elements cancel (each appears even times)

int countBits_naive(int n) {
    int count = 0;
    while (n) { count += n & 1; n >>= 1; }
    return count;
}

int countBits_BK(int n) {
    int count = 0;
    while (n) { n &= (n-1); count++; }   // n&(n-1) clears lowest set bit
    return count;
}
// For n = 0b10110100: 3 iterations (3 set bits) vs naive's 8 iterations

int count = __builtin_popcount(n);      // 32-bit integer
int count64 = __builtin_popcountll(n); // 64-bit integer
// Compiles to single hardware instruction (POPCNT) on modern CPUs

// Count total set bits in ALL numbers from 0 to n
long long totalSetBits(long long n) {
    long long count = 0;
    for (long long bit = 1; bit <= n; bit <<= 1) {
        long long cycle = bit << 1;          // Full cycle length
        count += (n / cycle) * bit;           // Complete cycles
        count += max(0LL, (n % cycle) - bit + 1);  // Partial cycle
    }
    return count;
}
// Time: O(log n), Space: O(1)

// For each i: dp[i] = dp[i>>1] + (i & 1)
// i>>1 removes the last bit; (i&1) accounts for that last bit
vector<int> countBits(int n) {
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++)
        dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}
// Time: O(n), Space: O(n)
// dp[6=0b110]: dp[3=0b11] + 0 = 2 + 0 = 2 ✓ (6 has 2 set bits)
// dp[7=0b111]: dp[3=0b11] + 1 = 2 + 1 = 3 ✓

// Each integer in [0, 2^n - 1] represents a subset
// Bit k = 1 means element k is in the subset
int n = 4;
vector<int> elems = {a, b, c, d};
 
for (int mask = 0; mask < (1 << n); mask++) {
    vector<int> subset;
    for (int k = 0; k < n; k++) {
        if (mask & (1 << k)) subset.push_back(elems[k]);
    }
    process(subset);
}
// Total iterations: 2^n subsets, n bits each → O(n × 2^n)
// Practical for n ≤ 20 (2^20 ≈ 10^6)

// Enumerate ALL non-empty subsets of mask in decreasing order
for (int sub = mask; sub > 0; sub = (sub-1) & mask) {
    process(sub);
    // (sub-1) & mask: decrements sub within the bits of mask
}
// Also process empty subset if needed: process(0)
 
// Example: mask = 0b1010 (elements at positions 1 and 3)
// Subsets: 0b1010 (both), 0b1000 (only 3), 0b0010 (only 1)
// Iteration: sub=1010 → sub=(1001)&1010=1000 → sub=(0111)&1010=0010 → sub=0001&1010=0 (stop)

// Enumerate all bitmasks with exactly k bits set, starting from the smallest
void enumerateKSubsets(int n, int k) {
    int mask = (1 << k) - 1;  // k consecutive ones: 0b...0111 (k ones)
 
    while (mask < (1 << n)) {
        process(mask);
 
        // Gosper's hack: next permutation of set bits
        int c = mask & (-mask);         // Lowest set bit
        int r = mask + c;               // Right bits carry
        mask = (((r ^ mask) >> 2) / c) | r;
    }
}
// Iterates all C(n, k) subsets in O(1) per step

// For n ≤ 40: split into two halves of n/2, enumerate each half's subsets,
// then combine. Reduces 2^n to 2 × 2^(n/2) = 2^(n/2+1).
 
// Example: Partition Array Into Two Equal-Sum Halves
// Half 1: generate all 2^20 subset sums → store in hash set
// Half 2: for each subset sum s, check if (target - s) exists in hash set

bool isPowerOf2(int n) {
    return n > 0 && (n & (n-1)) == 0;
    // n-1 flips the lowest set bit and all below it
    // If n is a power of 2: n = 1000...0, n-1 = 0111...1
    // n & (n-1) = 0 ✓
    // If not: some high bit and low bits remain → n & (n-1) != 0
}
 
// Powers of 2 up to 32 bits: 1,2,4,8,...,2^30,2^31(as unsigned)

// Round up n to the next power of 2
unsigned nextPow2(unsigned n) {
    if (n == 0) return 1;
    n--;           // Handle exact powers of 2
    n |= n >> 1;   // Fill in below MSB
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}
// Or simply: 1 << (32 - __builtin_clz(n-1))  for n > 1
// Example: n=6 → 8; n=8 → 8; n=9 → 16

// Fast modulo by power of 2:
int mod = n % 8;        // Slow: division
int fastMod = n & 7;    // Fast: n & (8-1) = n & 0b111
 
// Fast division by power of 2:
int div = n / 4;        // Slow
int fastDiv = n >> 2;   // Fast: right shift by log2(4) = 2
 
// Fast multiplication by power of 2:
int mul = n * 16;       // Standard
int fastMul = n << 4;   // Fast: left shift by log2(16) = 4
 
// Align n to next multiple of power of 2 (e.g., align to 16):
int aligned = (n + 15) & ~15;  // Round up to multiple of 16

int getSum(int a, int b) {
    while (b != 0) {
        int carry = (unsigned int)(a & b) << 1;  // Carry bits
        a = a ^ b;                                // Sum without carry
        b = carry;                                // Process carry next round
    }
    return a;
}
// Terminates because each iteration reduces set bits in b (carry shifts left,
// so eventually carry bits "fall off" the top)
// Time: O(1) — at most 32 iterations, Space: O(1)

// Hamming distance between two integers: number of differing bit positions
int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}
 
// Total Hamming distance across all pairs in an array
// Instead of O(n²), for each bit position k:
// contribution = (count of 0s at k) × (count of 1s at k)
int totalHammingDistance(vector<int>& nums) {
    int total = 0;
    for (int k = 0; k < 32; k++) {
        int ones = 0;
        for (int x : nums) ones += (x >> k) & 1;
        int zeros = nums.size() - ones;
        total += ones * zeros;    // Each (0,1) pair contributes 1 to distance
    }
    return total;
}
// Time: O(32n) = O(n), Space: O(1)

// AND of all numbers from m to n:
// Any two consecutive numbers n and n+1 differ in at least the lowest bit
// So AND of a range [m..n] = common prefix of m and n in binary
int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) {
        left >>= 1; right >>= 1;
        shift++;
    }
    return left << shift;  // Restore to original bit position
}
// Time: O(log n), Space: O(1)
// Explanation: m and n share a common bit prefix; all lower bits become 0
// because somewhere in [m,n] those bits have been 0 (by the range traversal)

// All numbers appear 3 times EXCEPT one (appears once).
// For each bit position, count total 1s. If count % 3 == 1 → single has this bit.
int singleNumber(vector<int>& nums) {
    int ones = 0, twos = 0;
    for (int x : nums) {
        ones  = (ones ^ x) & ~twos;   // Add to 'ones' if not already in 'twos'
        twos  = (twos ^ x) & ~ones;   // Add to 'twos' if not already in 'ones'
        // When count reaches 3: 'ones' and 'twos' both clear this bit
    }
    return ones;   // 'ones' holds bits that appeared exactly once (mod 3)
}
// Time: O(n), Space: O(1) — bit counter automaton

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}
// Time: O(n), Space: O(1)
// XOR: all duplicates cancel (a^a=0), single survives (0^b=b)

int missingNumber(vector<int>& nums) {
    int n = nums.size(), result = n;
    for (int i = 0; i < n; i++) result ^= i ^ nums[i];
    return result;
}
// Time: O(n), Space: O(1)
// Alternative: n*(n+1)/2 - accumulate(nums)

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) { n &= (n-1); count++; }   // Brian Kernighan: clear LSB each time
    return count;
    // Or: return __builtin_popcount(n);
}
// Time: O(set bits), Space: O(1)

vector<int> countBits(int n) {
    vector<int> dp(n+1, 0);
    for (int i = 1; i <= n; i++)
        dp[i] = dp[i>>1] + (i&1);   // Right-shift removes last bit, add it back
    return dp;
}
// Time: O(n), Space: O(n)

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);   // Shift result left, append LSB of n
        n >>= 1;
    }
    return result;
}
// Time: O(32) = O(1), Space: O(1)
 
// Divide & conquer bit reversal (O(1) with no loop):
uint32_t reverseBits_DC(uint32_t n) {
    n = (n >> 16) | (n << 16);                     // Swap 16-bit halves
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);   // Swap bytes
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);  // Swap nibbles
    n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);   // Swap 2-bit pairs
    n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);   // Swap adjacent bits
    return n;
}

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n-1)) == 0;
}
// Time: O(1), Space: O(1)
// Power of 2 has exactly one set bit → clearing LSB gives 0

int singleNumber(vector<int>& nums) {
    int ones = 0, twos = 0;
    for (int x : nums) {
        ones  = (ones ^ x) & ~twos;
        twos  = (twos ^ x) & ~ones;
    }
    return ones;
}
// Time: O(n), Space: O(1)
// Bit automaton: tracks count mod 3 per bit position

vector<int> singleNumber(vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;          // xorAll = a ^ b
    int diffBit = xorAll & (-xorAll);         // Lowest differing bit between a and b
    int a = 0, b = 0;
    for (int x : nums) {
        if (x & diffBit) a ^= x;             // Group 1
        else             b ^= x;             // Group 2
    }
    return {a, b};
}
// Time: O(n), Space: O(1)

int getSum(int a, int b) {
    while (b) {
        int carry = (unsigned int)(a & b) << 1;
        a ^= b;
        b = carry;
    }
    return a;
}
// Time: O(1) — max 32 iterations, Space: O(1)

int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) { left >>= 1; right >>= 1; shift++; }
    return left << shift;
}
// Time: O(log n), Space: O(1)
// Keep shifting right until both are equal (common prefix), then shift back

int totalHammingDistance(vector<int>& nums) {
    int total = 0;
    for (int k = 0; k < 32; k++) {
        int ones = 0;
        for (int x : nums) ones += (x >> k) & 1;
        total += ones * ((int)nums.size() - ones);
    }
    return total;
}
// Time: O(32n) = O(n), Space: O(1)

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> sub;
        for (int k = 0; k < n; k++)
            if (mask & (1 << k)) sub.push_back(nums[k]);
        result.push_back(sub);
    }
    return result;
}
// Time: O(n × 2^n), Space: O(n × 2^n)
// Compact alternative to backtracking; practical for n ≤ 20