Bit Manipulation Questions

Approach: Build a bitwise binary trie (0/1 children) for 32-bit unsigned integers. For each number insert its bits MSB→LSB. To query max XOR for a number, walk the trie preferring the opposite bit at each level to maximize result. Overall time O(n * W) where W=32.

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

// Binary trie node for bits 0 and 1
struct Node {
    int child[2];
    Node() { child[0] = child[1] = -1; }
};

struct BitwiseTrie {
    vector<Node> nodes;
    static constexpr int W = 32; // 32-bit integers

    BitwiseTrie() { nodes.emplace_back(); } // root

    void insert(uint32_t x) {
        int cur = 0;
        for (int b = W-1; b >= 0; --b) {
            int bit = (x >> b) & 1;
            if (nodes[cur].child[bit] == -1) {
                nodes[cur].child[bit] = nodes.size();
                nodes.emplace_back();
            }
            cur = nodes[cur].child[bit];
        }
    }

    // returns maximum xor of x with any number in trie
    uint32_t maxXor(uint32_t x) const {
        int cur = 0;
        uint32_t res = 0;
        for (int b = W-1; b >= 0; --b) {
            int bit = (x >> b) & 1;
            int want = bit ^ 1; // prefer opposite bit
            if (nodes[cur].child[want] != -1) {
                res |= (1u << b);
                cur = nodes[cur].child[want];
            } else {
                cur = nodes[cur].child[want ^ 1];
            }
        }
        return res;
    }
};

uint32_t findMaximumXOR(const vector<uint32_t>& nums) {
    if (nums.size() < 2) return 0;
    BitwiseTrie trie;
    trie.insert(nums[0]);
    uint32_t best = 0;
    for (size_t i = 1; i < nums.size(); ++i) {
        best = max(best, trie.maxXor(nums[i]));
        trie.insert(nums[i]);
    }
    return best;
}

// Example usage omitted for brevity.

Key points:

• Insert and query both take O(W) time; overall O(n * W).
• Space: worst-case O(n * W) nodes (each node small: two ints). For n up to 10^6 this can be memory heavy.

Memory optimizations:

• Use pool allocator and compact node representation (e.g., int32_t children indices or even packed 32-bit nodes).
• Use bitset-compressed tries (compress paths with single-child runs) — reduces nodes for clustered data.
• Build trie on 16-bit chunks (2-level trie) to reduce depth vs. table lookups trade-off.
• If memory critical, process array in blocks and compute local maxima with external memory techniques.

Trade-offs vs sorting-based methods:

• Sorting doesn't directly help maximize XOR; XOR lacks monotonicity used by two-pointer techniques. Alternatives: divide-and-conquer on bit prefixes (also O(n * W)) or use hashing of prefixes.
• Sorting uses O(n log n) time and O(1) extra memory (in-place), but won't give simpler XOR solution. Trie gives linear-in-W time and predictable behavior.
• If n is huge and memory limited, a hybrid: sort to group similar prefixes and only build tries per bucket, trading extra CPU and I/O for reduced peak memory.

Edge cases:

• Empty/one-element arrays -> 0
• Signed vs unsigned: use unsigned types to avoid sign-extension issues.

To convert between binary index k and its n-bit reflective Gray code, use the standard bitwise formulas:

• binary -> Gray: g = k ^ (k >> 1)
• Gray -> binary: iterate shifting XOR to accumulate bits: while (shift) b ^= (g >> shift)

Here's Python and C++ implementations plus explanation.

# python
def kth_to_gray(k: int) -> int:
    """Convert binary k to Gray code g = k ^ (k >> 1)."""
    return k ^ (k >> 1)

def gray_to_binary(g: int) -> int:
    """Convert Gray code to binary by XOR-accumulating shifted bits."""
    b = g
    shift = 1
    while (g >> shift) > 0:
        b ^= (g >> shift)
        shift += 1
    return b

// cpp
#include <cstdint>

uint64_t kth_to_gray(uint64_t k) {
    return k ^ (k >> 1);
}

uint64_t gray_to_binary(uint64_t g) {
    uint64_t b = g;
    for (uint64_t shift = 1; (g >> shift) != 0; ++shift)
        b ^= (g >> shift);
    return b;
}

Why correct:

• binary->Gray: reflective Gray code definition maps consecutive integers to codes differing by one bit; k ^ (k>>1) produces that mapping (MSB stays same, each lower Gray bit = XOR of adjacent binary bits).
• Gray->binary: binary bits are recovered by prefix-XOR of Gray bits: b_i = g_i XOR b_{i+1}..., implemented by XORing g with g shifted by 1,2,4,... (iterative shifts accumulate all higher-order contributions).

Complexity:

• Time: O(1) bitwise ops proportional to word size (O(log n) shifts); practically constant.
• Space: O(1).

Edge cases:

• Ensure k fits in chosen integer width (n ≤ word size). For large n use big integers. Functions work for n = 0 (return 0) and handle duplicates/leading zeros implicitly.

Approach:

• Right-shifting x by k (x >> k) uses an arithmetic right shift on most two's-complement machines: it rounds toward -∞ for negatives (it preserves the sign bit). C integer division (x / (1<<k)) rounds toward zero. To match C semantics without using division, add a bias for negative x before shifting: bias = (1U<<k) - 1; result = (x + (x < 0 ? bias : 0)) >> k.

Code (safe for 32-bit int, checks k range):

#include <stdint.h>
#include <limits.h>

int divideByPowerOfTwo(int x, int k) {
    // assume 0 <= k < sizeof(int)*8
    if (k <= 0) return x;
    if (k >= (int)(sizeof(int)*8)) { // shifting by width or more is undefined
        return 0; // or handle as needed
    }

    // compute bias using unsigned to avoid UB when k == 31
    uint32_t bias = ((1u << k) - 1u);
    // If x is negative, add bias to round toward zero after arithmetic shift
    int adjusted = x;
    if (x < 0) {
        adjusted = x + (int)bias;
    }
    return adjusted >> k; // arithmetic right shift preserves sign on two's-complement
}

Key points / reasoning:

• For positive x both truncating division and arithmetic shift give same result.
• For negative x, arithmetic right shift rounds down (toward -∞). Example: x = -3, k = 1:
  • -3 >> 1 (arithmetic) => -2 (since -3/2 = -1.5 rounded down)
  • Desired C division -3/2 => -1 (rounded toward zero)
• Adding bias = 2^k - 1 before shifting corrects the result for negatives: (-3 + 1) >> 1 = -1.
• Use unsigned when building bias to avoid overflow/UB for large k; guard against shifting by >= width.

Complexity:

• Time O(1), Space O(1).

Edge cases:

• k == 0 => return x.
• k >= bit-width => shifting undefined; handle explicitly.
• Relies on arithmetic right shift (common on two's-complement systems). If target uses logical shift for signed, use unsigned casts: ((unsigned)x + bias) >> k with sign-correct conversion.

Approach summary:
Use bit-parallel branch-and-bound on an undirected graph with n ≤ 50 by storing adjacency lists as 64-bit masks (uint64_t). Search for max independent set (or max clique on complement) using recursive backtracking over a candidate set (bitmask). At each node use a greedy coloring on the candidate set (with bit operations) to compute an upper bound; prune branches where current_size + bound ≤ best. Order vertices by degree/degenerate order to improve pruning. Bit operations (&, ^, -) make intersections and removals constant-time per machine word.

C++ implementation (max independent set):

#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;

int best = 0;
int n;
vector<u64> adj; // adjacency masks

// Count trailing ones/popcount helpers
inline int popcnt(u64 x){ return __builtin_popcountll(x); }
inline int lsb_index(u64 x){ return __builtin_ctzll(x); }

void expand(u64 cand, int sz){
    if(cand==0){
        best = max(best, sz);
        return;
    }
    // greedy coloring to get upper bound
    int color_bound = 0;
    u64 rem = cand;
    while(rem){
        ++color_bound;
        u64 used = 0;
        u64 layer = rem;
        while(layer){
            int v = lsb_index(layer);
            u64 bit = 1ULL<<v;
            if(!(used & bit)){
                // select v in this color class
                used |= adj[v] | bit;
                rem &= ~bit;
            }
            layer &= layer - 1; // clear lsb
            layer &= ~used; // skip vertices adjacent to used
        }
    }
    if(sz + color_bound <= best) return;

    // choose pivot: vertex with maximal degree in cand
    int u = -1, maxd = -1;
    u64 tmp = cand;
    while(tmp){
        int v = lsb_index(tmp); tmp &= tmp-1;
        int d = popcnt(cand & adj[v]);
        if(d > maxd){ maxd = d; u = v; }
    }
    // branch on candidates not adjacent to pivot first (heuristic)
    u64 branch = cand & ~adj[u];
    while(branch){
        int v = lsb_index(branch);
        u64 bit = 1ULL<<v;
        branch &= branch - 1;
        expand(cand & ~adj[v] & ~bit, sz+1);
        cand &= ~bit;
        if(sz + popcnt(cand) <= best) return;
    }
}

int max_independent_set(){
    best = 0;
    expand((n==64?~0ULL:((1ULL<<n)-1)), 0);
    return best;
}

Key concepts:

• Represent graph as u64 adjacency masks: fast set ops with &, |, ~.
• Candidate set intersection: cand & ~adj[v] removes neighbors when picking v.
• Greedy coloring on bitsets yields a cheap upper bound for pruning.
• Pivoting and ordering (highest-degree pivot, degeneracy ordering) reduce branching.

Complexity:
Worst-case exponential (O(2^(n/3)) or worse), but pruning via coloring usually makes it feasible for n ≤ 50 on real inputs. Each recursion uses bit-parallel ops (O(1) per 64-bit word) and popcount/ctz hardware.

Practical tips:

• Precompute degeneracy ordering and relabel vertices to reduce branching.
• Use __builtin_popcountll and ctz for speed.
• Inline and compile with -O3.
• Use iterative stack if recursion depth is a concern.
• For cliques, run algorithm on graph complement.
• Cache small bitset bounds or use memoization on small cand sets to prune repeated states.

Approach (high level)

1. Choose instruction strategy: if AVX512_VPOPCNTDQ available use it (direct 64-bit popcount vector), otherwise use AVX2 PSHUFB-based byte-wise lookup (popcount by nibble/byte table).
2. Process large buffer in wide vectors (512-bit or 256-bit) in a tight loop, aggregate lane sums into 64-bit accumulators, handle alignment and tail.

AVX512_VPOPCNTDQ algorithm

• Load 512-bit block (8×64-bit)
• vpcountdq to get popcount per 64-bit lane
• vaddq to accumulate into running 64-bit sum registers
• Reduce vector periodically into scalar accumulator to avoid overflow
  Benefits: simplest, minimal instruction count, highest throughput on supporting CPUs.

AVX2 PSHUFB (byte-wise lookup) algorithm

• Precompute 16-entry nibble-popcount table in a 128-bit vector (or 256/512 replicated)
• For each 256-bit load:
  • Split bytes into low and high nibbles: lo = byte & 0x0F; hi = (byte >> 4) & 0x0F
  • Use VPSHUFB (PSHUFB) to lookup popcount for lo and hi
  • Add lo_count + hi_count → per-byte popcounts
  • Horizontally sum bytes into 64-bit accumulators (use VPADDB -> VPADDD/VPADDQ reductions)
    Benefits: works on older hardware, good throughput, avoids costly scalar popcount.

Alignment and tail handling

• Align main loop to vector-width for best throughput; use unaligned loads only if CPU supports them efficiently (modern x86 allows fast unaligned loads).
• Prologue: process few bytes to reach aligned address (optional).
• Tail: process remaining < vector-width bytes with smaller vector or scalar popcount (use builtin __builtin_popcountll for last few 64-bit words).

Trade-offs

• AVX512_VPOPCNTDQ: simpler, lower instruction count, but only on recent CPUs and can be power-hungry; avoids complex reductions.
• PSHUFB lookup: portable to AVX2, high throughput but more instructions (masking, shifting, two shuffles, adds), requires careful reduction to avoid latency stalls.
• Memory bandwidth vs compute: for huge buffers, memory-bound — wider vectors may not help; measure with perf counters.

Example pseudocode (AVX2 nibble lookup)

// pseudocode
const __m128i tbl = ...; // 16-byte nibble popcount table
while (n >= 32) {
  v = _mm256_loadu_si256(ptr);
  lo = v & 0x0F;
  hi = (v >> 4) & 0x0F;
  cnt_lo = _mm256_shuffle_epi8(tbl256, lo);
  cnt_hi = _mm256_shuffle_epi8(tbl256, hi);
  cnt = _mm256_add_epi8(cnt_lo, cnt_hi);
  // widen and horizontally sum into 64-bit accumulators
  accumulate(cnt);
  ptr += 32; n -= 32;
}
process_tail();

Performance tips

• Unroll loop, accumulate into multiple registers to hide latency.
• Reduce less frequently (every few iterations) to avoid vector-to-scalar bottleneck.
• Benchmark on target CPU; prefer instruction set that yields best real throughput.