Bit Manipulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// toString(2) gives binary. padStart lines it up so patterns are visible.
const bits = n => (n >>> 0).toString(2).padStart(8, '0');

for (const n of [0, 1, 2, 3, 4, 5, 8, 15, 16, 255]) {
  console.log(String(n).padStart(3), '=', bits(n));
}

console.log('');
console.log('5     =', bits(5), ' (4 + 1)');
console.log('3     =', bits(3), ' (2 + 1)');
console.log('5 & 3 =', bits(5 & 3), ' both bits set    ->', 5 & 3);
console.log('5 | 3 =', bits(5 | 3), ' either bit set   ->', 5 | 3);
console.log('5 ^ 3 =', bits(5 ^ 3), ' exactly one set  ->', 5 ^ 3);
console.log('5 << 1=', bits(5 << 1), ' shift left = x2  ->', 5 << 1);
console.log('5 >> 1=', bits(5 >> 1), ' shift right = /2 ->', 5 >> 1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22console.log('(-5).toString(2)      =', (-5).toString(2), '  <- misleading');
console.log('(-5 >>> 0).toString(2)=', (-5 >>> 0).toString(2), '  <- the actual 32 bits');
console.log('');

// Two's complement: to negate, flip every bit and add one.
console.log('~5      =', ~5, '  = -(5) - 1');
console.log('~0      =', ~0, '  every bit set');
console.log('~-1     =', ~-1);
console.log('-5 === ~5 + 1 ?', -5 === ~5 + 1);
console.log('');

// >> keeps the sign, >>> does not.
console.log('-8 >> 1  =', -8 >> 1, ' arithmetic shift, stays negative');
console.log('-8 >>> 1 =', -8 >>> 1, ' logical shift, becomes huge');
console.log('');

// The 32-bit boundary. This is the trap.
console.log('2 ** 31        =', 2 ** 31);
console.log('1 << 31        =', 1 << 31, ' <- overflowed into negative');
console.log('1 << 32        =', 1 << 32, ' <- shift count wraps: 32 % 32 = 0');
console.log('2 ** 31 | 0    =', 2 ** 31 | 0);
console.log('2 ** 53 | 0    =', 2 ** 53 | 0, ' <- upper bits simply discarded');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18const bits = n => (n >>> 0).toString(2).padStart(8, '0');

const getBit    = (n, i) => (n >> i & 1) === 1;      // is bit i set?
const setBit    = (n, i) => n | (1 << i);            // force bit i to 1
const clearBit  = (n, i) => n & ~(1 << i);           // force bit i to 0
const toggleBit = (n, i) => n ^ (1 << i);            // flip bit i

let value = 0b1010;                                   // 10
console.log('start        ', bits(value), '=', value);
console.log('getBit 1     ', getBit(value, 1));       // true
console.log('getBit 2     ', getBit(value, 2));       // false
console.log('setBit 0     ', bits(setBit(value, 0)), '=', setBit(value, 0));
console.log('clearBit 3   ', bits(clearBit(value, 3)), '=', clearBit(value, 3));
console.log('toggleBit 1  ', bits(toggleBit(value, 1)), '=', toggleBit(value, 1));
console.log('');

// A mask of the low k bits: (1 << k) - 1.
for (const k of [1, 3, 5, 8]) console.log(`low ${k} bits mask:`, bits((1 << k) - 1));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20const bits = n => (n >>> 0).toString(2).padStart(8, '0');

// n & (n - 1) clears the lowest set bit.
console.log('n & (n-1) clears the lowest set bit:');
for (const n of [12, 10, 8, 7]) {
  console.log(`  ${bits(n)} & ${bits(n - 1)} = ${bits(n & (n - 1))}   (${n} -> ${n & (n - 1)})`);
}
console.log('');

// n & -n isolates the lowest set bit.
console.log('n & -n isolates the lowest set bit:');
for (const n of [12, 10, 8, 7]) {
  console.log(`  ${bits(n)} & ${bits(-n)} = ${bits(n & -n)}   (${n} -> ${n & -n})`);
}
console.log('');

// The first gives a power-of-two test in one line.
const isPowerOfTwo = n => n > 0 && (n & (n - 1)) === 0;
console.log('powers of two up to 20:', Array.from({ length: 21 }, (_, i) => i).filter(isPowerOfTwo));
console.log('isPowerOfTwo(0):', isPowerOfTwo(0), '(the n > 0 guard matters)');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32// 1. Check all 32 positions.
function countLoop(n) {
  let count = 0;
  for (let i = 0; i < 32; i++) if (n >> i & 1) count++;
  return count;
}

// 2. Clear the lowest set bit repeatedly: one iteration per set bit.
function countKernighan(n) {
  let count = 0;
  while (n !== 0) { n &= n - 1; count++; }
  return count;
}

// 3. Dynamic programming: bits(n) = bits(n >> 1) + (n & 1).
function countUpTo(limit) {
  const counts = new Array(limit + 1).fill(0);
  for (let i = 1; i <= limit; i++) counts[i] = counts[i >> 1] + (i & 1);
  return counts;
}

for (const n of [0, 1, 7, 8, 255, 1023]) {
  console.log(`${String(n).padStart(4)}: loop ${countLoop(n)}, kernighan ${countKernighan(n)}`);
}
console.log('counts 0..15:', countUpTo(15).join(' '));

// On a sparse number the difference in work is large.
const sparse = 1 << 30;
let loopSteps = 0, kernSteps = 0;
for (let i = 0; i < 32; i++) loopSteps++;
let temp = sparse; while (temp !== 0) { temp &= temp - 1; kernSteps++; }
console.log(`for 2^30: loop does ${loopSteps} iterations, Kernighan does ${kernSteps}`);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25console.log('x ^ x === 0    ', (7 ^ 7) === 0, '  a value cancels itself');
console.log('x ^ 0 === x    ', (7 ^ 0) === 7, '  zero is the identity');
console.log('order-free     ', (1 ^ 2 ^ 3) === (3 ^ 1 ^ 2), '  commutative and associative');
console.log('');

// Every number appears twice except one. XOR everything: pairs cancel.
function singleNumber(nums) {
  let result = 0;
  for (const n of nums) result ^= n;
  return result;
}
console.log('singleNumber([4,1,2,1,2]) =', singleNumber([4, 1, 2, 1, 2]));
console.log('singleNumber([2,2,7])     =', singleNumber([2, 2, 7]));
console.log('singleNumber([9])         =', singleNumber([9]));
console.log('');

// The missing number from 0..n: XOR the indices and the values together.
function missingNumber(nums) {
  let result = nums.length;                 // n itself is never an index
  for (let i = 0; i < nums.length; i++) result ^= i ^ nums[i];
  return result;
}
console.log('missingNumber([3,0,1])  =', missingNumber([3, 0, 1]));
console.log('missingNumber([0,1])    =', missingNumber([0, 1]));
console.log('missingNumber([1])      =', missingNumber([1]));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34function singleNumberTwice(nums) {
  // XOR everything: the pairs vanish, leaving a ^ b for the two singles.
  let xorBoth = 0;
  for (const n of nums) xorBoth ^= n;

  // a ^ b has a 1 wherever a and b differ. Isolate the lowest such bit.
  const diffBit = xorBoth & -xorBoth;

  // That bit splits the array into two groups, each with one single number.
  let first = 0, second = 0;
  for (const n of nums) {
    if (n & diffBit) first ^= n;
    else second ^= n;
  }
  return [first, second].sort((x, y) => x - y);
}

console.log(singleNumberTwice([1, 2, 1, 3, 2, 5]));     // [3,5]
console.log(singleNumberTwice([4, 1, 4, 6]));           // [1,6]
console.log(singleNumberTwice([-1, 0, -1, 2]));         // [0,2]

// A number appearing three times needs a different idea: count each bit
// position and take the count modulo 3.
function singleNumberThrice(nums) {
  let result = 0;
  for (let bit = 0; bit < 32; bit++) {
    let sum = 0;
    for (const n of nums) sum += (n >> bit) & 1;
    if (sum % 3 !== 0) result |= 1 << bit;
  }
  return result | 0;                        // keep it a signed 32-bit int
}
console.log('appears once among triples:', singleNumberThrice([2, 2, 3, 2]));      // 3
console.log('with a negative:           ', singleNumberThrice([-2, -2, 1, -2]));   // 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function subsets(nums) {
  const n = nums.length;
  const results = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    results.push(subset);
  }
  return results;
}

console.log(subsets(['a', 'b', 'c']));
console.log('count:', subsets([1, 2, 3, 4]).length, '= 2^4');
console.log('empty input:', subsets([]));
console.log('');

// The masks themselves, printed alongside their subsets.
const items = ['x', 'y', 'z'];
for (let mask = 0; mask < 8; mask++) {
  const chosen = items.filter((_, i) => mask & (1 << i));
  console.log(`mask ${mask.toString(2).padStart(3, '0')} -> [${chosen.join(',')}]`);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40// Instead of a boolean array, one integer. Common in DP over subsets.
function permutationsBitmask(nums) {
  const n = nums.length, results = [];
  const full = (1 << n) - 1;

  function walk(used, current) {
    if (used === full) { results.push([...current]); return; }
    for (let i = 0; i < n; i++) {
      if (used & (1 << i)) continue;                 // already taken
      current.push(nums[i]);
      walk(used | (1 << i), current);                // no undo needed: new value
      current.pop();
    }
  }
  walk(0, []);
  return results;
}
console.log(permutationsBitmask([1, 2, 3]));
console.log('');

// 26 lowercase letters fit in one integer, so "do these words share a letter?"
// becomes a single AND.
function maxProductNoSharedLetters(words) {
  const masks = words.map(w => {
    let mask = 0;
    for (const ch of w) mask |= 1 << (ch.charCodeAt(0) - 97);
    return mask;
  });

  let best = 0;
  for (let i = 0; i < words.length; i++)
    for (let j = i + 1; j < words.length; j++)
      if ((masks[i] & masks[j]) === 0)               // no letter in common
        best = Math.max(best, words[i].length * words[j].length);
  return best;
}

console.log(maxProductNoSharedLetters(['abcw', 'baz', 'foo', 'bar', 'xtfn', 'abcdef']));   // 16
console.log(maxProductNoSharedLetters(['a', 'ab', 'abc', 'd', 'cd', 'bcd', 'abcd']));      // 4
console.log(maxProductNoSharedLetters(['a', 'aa', 'aaa']));                                // 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function add(a, b) {
  // carry holds the bits that need to move left; loop until nothing carries.
  while (b !== 0) {
    const carry = (a & b) << 1;      // both bits set -> carry into the next place
    a = a ^ b;                        // exactly one bit set -> sum bit
    b = carry;
  }
  return a;
}

console.log('add(3, 5)   =', add(3, 5));
console.log('add(0, 7)   =', add(0, 7));
console.log('add(-3, 5)  =', add(-3, 5), ' two\'s complement handles it');
console.log('add(-3, -5) =', add(-3, -5));
console.log('add(2**30, 2**30) =', add(2 ** 30, 2 ** 30), ' overflows 32 bits');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n >> i & 1);     // pull the lowest, push it high
  }
  return result >>> 0;                         // report it as unsigned
}

const show = n => (n >>> 0).toString(2).padStart(32, '0');
console.log('in :', show(43261596));
console.log('out:', show(reverseBits(43261596)));
console.log('   =', reverseBits(43261596));
console.log('');
console.log('in :', show(1));
console.log('out:', show(reverseBits(1)), '=', reverseBits(1));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function grayCode(n) {
  const result = [];
  for (let i = 0; i < (1 << n); i++) result.push(i ^ (i >> 1));
  return result;
}

const showBits = (n, width) => (n >>> 0).toString(2).padStart(width, '0');
console.log('n = 2:', grayCode(2));
console.log('n = 3:', grayCode(3));
console.log('');
grayCode(3).forEach((v, i) => console.log(`  ${i}: ${showBits(v, 3)}`));

// Verify the defining property.
const codes = grayCode(4);
const singleBitApart = codes.every((v, i) => {
  if (i === 0) return true;
  const diff = v ^ codes[i - 1];
  return (diff & (diff - 1)) === 0 && diff !== 0;      // exactly one bit differs
});
console.log('');
console.log('every adjacent pair differs by exactly one bit:', singleBitApart);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// BigInt supports the same operators with no width limit. Literals end in n.
const big = 1n << 40n;
console.log('1n << 40n      =', big.toString());
console.log('as binary      =', big.toString(2).length, 'bits wide');
console.log('1 << 40 (Number) =', 1 << 40, '<- wrong, shift wrapped to 8');
console.log('');

console.log('BigInt xor:', (0xffffffffffn ^ 0x0000000001n).toString(16));
console.log('BigInt and:', (0b1100n & 0b1010n).toString(2));
console.log('');

// You cannot mix BigInt and Number in an operation.
try {
  console.log(1n + 1);
} catch (err) {
  console.log('1n + 1 ->', err.constructor.name + ':', err.message);
}
console.log('explicit conversion works:', 1n + BigInt(1), 'and', Number(1n) + 1);
console.log('');
console.log('BigInt has no >>> operator: it is unbounded, so there is nothing to fill.');