// ─────────────────────────────────────────────────────────────────────────────
// BIT MANIPULATION
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : operate on the binary representation directly; O(1) tricks and compact state.
// TELL   : "without using + / *", "appears once / twice / three times", "number of 1 bits", "power of two",
//          "subsets of a small set", "XOR", "O(1) space" where counting would be natural.
// SAY    : bitmask, set / clear / toggle / test a bit, lowest set bit, popcount (Hamming weight),
//          Brian Kernighan's algorithm, XOR cancellation, two's complement, arithmetic vs logical shift.
// BIG-O  : O(1) per op on 32-bit ints; O(number of set bits) for Kernighan; O(2^n * n) for subset enumeration.
// NOTE   : JS bitwise ops coerce to 32-BIT SIGNED ints. 1 << 31 === -2147483648; 2**31 | 0 is negative.
//          For > 2^31 use BigInt (1n << 40n) or Math (Math.floor(x / 2**k)). >>> 0 reinterprets as unsigned 32.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 0. Operators & idioms
//   a & b   AND          a | b   OR           a ^ b   XOR          ~a   NOT (= -a - 1)
//   a << k  shift left (x 2^k)    a >> k  arithmetic shift right (keeps sign)    a >>> k  logical shift right (zero-fill)
//   test bit i    : (n >> i) & 1          set bit i   : n | (1 << i)
//   clear bit i   : n & ~(1 << i)         toggle bit i: n ^ (1 << i)
//   n & (n - 1)   : clears the LOWEST set bit          n & -n     : isolates the LOWEST set bit
//   power of two  : n > 0 && (n & (n - 1)) === 0       x ^ x = 0, x ^ 0 = x  => XOR cancels pairs
//   swap          : a ^= b; b ^= a; a ^= b (don't; use destructuring)   parity: popcount & 1
const getBit = (n, i) => (n >> i) & 1;
const setBit = (n, i) => n | (1 << i);
const clearBit = (n, i) => n & ~(1 << i);
const toggleBit = (n, i) => n ^ (1 << i);
assert.equal(getBit(0b1010, 1), 1);
assert.equal(getBit(0b1010, 0), 0);
assert.equal(setBit(0b1010, 0), 0b1011);
assert.equal(clearBit(0b1010, 3), 0b0010);
assert.equal(toggleBit(0b1010, 1), 0b1000);
assert.equal(0b1100 & (0b1100 - 1), 0b1000); // clears lowest set bit
assert.equal(0b1100 & -0b1100, 0b0100); // isolates lowest set bit
const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0;
assert.equal(isPowerOfTwo(64), true);
assert.equal(isPowerOfTwo(0), false);
assert.equal(isPowerOfTwo(96), false);
assert.equal(~5, -6);
assert.equal(-8 >> 1, -4); // arithmetic
assert.equal(-8 >>> 28, 15); // logical: 0xFFFFFFF8 >>> 28
assert.equal(1 << 31, -2147483648); // the 32-bit trap
assert.equal((1 << 31) >>> 0, 2147483648); // unsigned view
assert.equal(1n << 40n, 1099511627776n); // BigInt for wide shifts

// ── 1. Single number (every other appears twice)  —  XOR everything; pairs cancel  —  O(n) / O(1)
const singleNumber = (nums) => nums.reduce((a, x) => a ^ x, 0);
assert.equal(singleNumber([4, 1, 2, 1, 2]), 4);
assert.equal(singleNumber([1]), 1);
assert.equal(singleNumber([-3, 7, 7]), -3);

// ── 2. Single number II (others appear three times) sketch  —  per bit, count set bits mod 3; rebuild answer. Handles negatives via | 0  —  O(32n) / O(1)
function singleNumberII(nums) {
  let out = 0;
  for (let i = 0; i < 32; i++) {
    let cnt = 0;
    for (const x of nums) cnt += (x >> i) & 1;
    if (cnt % 3) out |= 1 << i;
  }
  return out | 0; // force signed 32-bit interpretation
}
assert.equal(singleNumberII([2, 2, 3, 2]), 3);
assert.equal(singleNumberII([0, 1, 0, 1, 0, 1, 99]), 99);
assert.equal(singleNumberII([-2, -2, -2, 5]), 5);

// ── 3. Number of 1 bits (Hamming weight), Brian Kernighan  —  loop n &= n - 1 once per set bit  —  O(set bits)
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) { n &= n - 1; count++; }
  return count;
}
assert.equal(hammingWeight(0b1011), 3);
assert.equal(hammingWeight(0), 0);
assert.equal(hammingWeight(-1), 32); // all 32 bits set in two's complement

// ── 4. Counting bits 0..n (DP)  —  bits[i] = bits[i >> 1] + (i & 1); or bits[i & (i-1)] + 1  —  O(n) / O(n)
function countBits(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;
}
assert.deepEqual(countBits(5), [0, 1, 1, 2, 1, 2]);
assert.deepEqual(countBits(0), [0]);

// ── 5. Reverse bits (32-bit unsigned)  —  shift result left, OR in lowest bit of n, shift n right (logical)  —  O(32)
function reverseBits(n) {
  let out = 0;
  for (let i = 0; i < 32; i++) { out = (out << 1) | (n & 1); n >>>= 1; }
  return out >>> 0; // unsigned result
}
assert.equal(reverseBits(0b00000010100101000001111010011100), 964176192);
assert.equal(reverseBits(0), 0);
assert.equal(reverseBits(1), 2147483648);

// ── 6. Missing number via XOR  —  XOR all indices 0..n and all values; the unmatched one survives  —  O(n) / O(1)
function missingNumber(nums) {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];
  return x;
}
assert.equal(missingNumber([3, 0, 1]), 2);
assert.equal(missingNumber([0]), 1);
assert.equal(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]), 8);

// ── 7. Sum of two integers without +  —  sum = a ^ b (no carry); carry = (a & b) << 1; repeat until carry 0  —  O(32)
function getSum(a, b) {
  while (b !== 0) { const carry = (a & b) << 1; a ^= b; b = carry; }
  return a;
}
assert.equal(getSum(1, 2), 3);
assert.equal(getSum(-2, 3), 1);
assert.equal(getSum(0, 0), 0);

// ── 8. Subsets via bitmask enumeration  —  mask 0..2^n-1; bit i set => include nums[i]  —  O(2^n * n)
function subsets(nums) {
  const n = nums.length, out = [];
  for (let mask = 0; mask < 1 << n; mask++) {
    const sub = [];
    for (let i = 0; i < n; i++) if (mask & (1 << i)) sub.push(nums[i]);
    out.push(sub);
  }
  return out;
}
assert.deepEqual(subsets([1, 2, 3]), [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]);
assert.deepEqual(subsets([]), [[]]);
// Iterate submasks of a mask: for (let s = mask; s > 0; s = (s - 1) & mask) ...  (O(3^n) over all masks)

// ── 9. Bitmask as visited-set for small n (n <= ~20)  —  visited | (1 << i); full when visited === (1 << n) - 1
//        Example: count Hamiltonian paths from node 0 in a tiny graph via DFS over (node, mask). Memo key = node * 2^n + mask.
function countHamiltonianPaths(adj) {
  const n = adj.length, full = (1 << n) - 1, memo = new Map();
  const dfs = (u, mask) => {
    if (mask === full) return 1;
    const key = u * (1 << n) + mask;
    if (memo.has(key)) return memo.get(key);
    let total = 0;
    for (const v of adj[u]) if (!(mask & (1 << v))) total += dfs(v, mask | (1 << v));
    memo.set(key, total);
    return total;
  };
  return dfs(0, 1); // start at node 0, visited = {0}
}
const triangle = [[1, 2], [0, 2], [0, 1]];
assert.equal(countHamiltonianPaths(triangle), 2); // 0-1-2, 0-2-1
const path3 = [[1], [0, 2], [1]];
assert.equal(countHamiltonianPaths(path3), 1); // 0-1-2 only
assert.equal(countHamiltonianPaths([[]]), 1); // single node: already full

// ── 10. > 2^31 guard  —  bitwise truncates; use Math.floor / BigInt for big values
assert.equal((2 ** 32 + 5) | 0, 5); // truncated silently
assert.equal(Math.floor((2 ** 40 + 7) / 2 ** 40), 1); // "shift" with Math for big numbers
assert.equal(BigInt(2 ** 40) >> 38n, 4n);
assert.equal(Number.MAX_SAFE_INTEGER, 2 ** 53 - 1); // beyond this, integers lose precision anyway

console.log('ok: algorithms/bit-manipulation.js');