Bit Manipulation

// Template 1: masks. 1 << i is a number with only bit i set; combine it with &, | and ^
// to test, set, clear or toggle that one bit and leave every other bit alone.
// Bitwise operators work on 32-bit integers, so i must be between 0 and 31.
export function getBit(n, i) {
  return (n >> i) & 1;        // 0 or 1
}

export function setBit(n, i) {
  return n | (1 << i);
}

export function clearBit(n, i) {
  return n & ~(1 << i);       // ~ flips the mask: every bit is 1 except bit i
}

export function toggleBit(n, i) {
  return n ^ (1 << i);
}

// Walk all 32 bits from the lowest up, building the reversed number. >>> keeps everything unsigned.
export function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;
  }
  return result >>> 0;
}

// Template 2: XOR cancellation. x ^ x = 0, x ^ 0 = x, and the order doesn't matter, so
// XOR-ing a list leaves exactly the bits of the values that appear an odd number of times.
export function xorAll(nums) {
  let acc = 0;
  for (const x of nums) acc ^= x;
  return acc;
}

// Missing number in 0..n: XOR every index and value; present numbers appear twice and cancel.
export function missingNumber(nums) {
  let acc = nums.length;
  for (let i = 0; i < nums.length; i++) acc ^= i ^ nums[i];
  return acc;
}

// Two values appear once, all others twice. a ^ b is non-zero, so pick a bit where a and b differ
// and XOR each half separately: each half then holds exactly one of the two singles.
export function twoSingles(nums) {
  const both = xorAll(nums);
  const bit = both & -both;               // lowest set bit of a ^ b
  let a = 0;
  for (const x of nums) if (x & bit) a ^= x;
  return [a, both ^ a].sort((x, y) => x - y);
}

// Template 3: n & (n - 1) removes the lowest set bit. n - 1 flips that bit to 0 and every 0 below
// it to 1, so the AND keeps the higher bits and wipes out the rest.
export function popcount(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;                 // one iteration per set bit
    count++;
  }
  return count;
}

// A power of two has exactly one set bit, so removing it leaves 0.
export function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

// n & -n keeps only the lowest set bit (-n is ~n + 1 in two's complement).
export function lowestSetBit(n) {
  return n & -n;
}

// Counts for every number 0..n: i >> 1 is i without its last bit, already computed.
export function countBitsUpTo(n) {
  const bits = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
  return bits;
}

// Template 4: subsets as bitmasks. Bit i of mask says whether items[i] is in the subset, so
// counting mask from 0 to 2^n - 1 lists every subset exactly once. Keep n at 30 or less:
// 1 << 31 is already negative in JavaScript.
export function subsets(items) {
  const n = items.length;
  const out = [];
  for (let mask = 0; mask < 1 << n; mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(items[i]);
    }
    out.push(subset);
  }
  return out;
}

// Every submask of mask, from mask itself down to 0. (s - 1) & mask jumps to the next smaller
// number that only uses bits of mask.
export function submasks(mask) {
  const out = [];
  for (let s = mask; ; s = (s - 1) & mask) {
    out.push(s);
    if (s === 0) break;
  }
  return out;
}