Bit Tricks in JavaScript, Tested Against Every Input They Claim to Cover

Single Number, Missing Number and Counting Bits are small enough that you do not have to trust anyone's explanation, including mine. The input spaces are enumerable. So I enumerated them: 38,600 array shapes for the XOR trick, 31,701 index configurations for Missing Number, all 1,048,577 values from 0 to 2^20 for the DP, and contiguous million-value blocks sitting on top of 2^31 and 2^32 for the three popcount loops.

Most of it holds. The interesting part is the four places it stops holding, all of which are the same place: JavaScript hands every bitwise operator a signed 32-bit integer, and the operators hand back a signed 32-bit integer, and nothing in between tells you that your 2^40 went missing.

Ground truth before anything else

You cannot check a bit trick with another bit trick. The reference has to be arithmetic that does not truncate, which in JavaScript means BigInt.

const assert = (cond, msg) => { if (!cond) throw new Error(msg); };
 
// Reference popcount: no 32-bit operators anywhere.
const popcountRef = (x) => {
  let b = BigInt(x);
  assert(b >= 0n, `popcountRef needs a non-negative integer, got ${x}`);
  let c = 0;
  while (b > 0n) { c += Number(b & 1n); b >>= 1n; }
  return c;
};
 
assert(popcountRef(0) === 0, "0 has no set bits");
assert(popcountRef(255) === 8, "255 is eight ones");
assert(popcountRef(2 ** 40) === 1, "a single high bit");
assert(popcountRef(Number.MAX_SAFE_INTEGER) === 53, "2^53 - 1 is fifty-three ones");
console.log("reference popcount ok");

BigInt shifts are arbitrary-precision, so popcountRef(Number.MAX_SAFE_INTEGER) is 53. Hold on to that number — three of the four routines below will tell you it is 32 or 1.

Single Number: 38,600 shapes clean, then negative

XOR is self-inverse and commutative, so XOR-ing an array where everything is paired except one element cancels the pairs in any order and leaves the survivor. That claim is small enough to test completely at small sizes, so there is no reason to take it on faith.

const singleNumberXor = (nums) => nums.reduce((acc, n) => acc ^ n, 0);
 
// Every single-element choice over 0..9, crossed with every subset of the
// remaining nine values up to four pairs, crossed with every rotation and
// its reversal.
let shapes = 0;
for (let single = 0; single <= 9; single++) {
  const pool = [...Array(10).keys()].filter((x) => x !== single);
  const subsets = [[]];
  for (const x of pool) {
    const n = subsets.length;
    for (let i = 0; i < n; i++) {
      if (subsets[i].length < 4) subsets.push([...subsets[i], x]);
    }
  }
  for (const sub of subsets) {
    const base = [single, ...sub.flatMap((x) => [x, x])];
    for (let r = 0; r < base.length; r++) {
      const rot = [...base.slice(r), ...base.slice(0, r)];
      for (const arr of [rot, [...rot].reverse()]) {
        shapes++;
        assert(singleNumberXor(arr) === single, `wrong for ${arr}`);
      }
    }
  }
}
console.log(`singleNumberXor: ${shapes} shapes, 0 failures`);

That prints singleNumberXor: 38600 shapes, 0 failures. Zero is the right number of failures and it is also a useless number, because every value in those arrays fits in nine bits. Push the survivor up past the sign bit:

for (const s of [2 ** 30, 2 ** 31 - 1, 2 ** 31, 2 ** 31 + 1, 2 ** 32, 2 ** 32 + 7]) {
  console.log(s, "->", singleNumberXor([7, 7, s]));
}
// 1073741824 -> 1073741824
// 2147483647 -> 2147483647
// 2147483648 -> -2147483648
// 2147483649 -> -2147483647
// 4294967296 -> 0
// 4294967303 -> 7

The last two lines are the ones that would ruin an afternoon. 4294967296 comes back as 0, which does not mean "the answer is zero" so much as "there is no unpaired element in this array" — a legitimate answer to a different question. 4294967303 comes back as 7, which is one of the paired values. Nothing throws. ^ also truncates fractions on the way in, so singleNumberXor([1.5, 1.5, 2.5]) is 2.

LeetCode caps the inputs at plus or minus 30,000, so the trick is correct for the problem as stated. It is not correct for "find the unpaired number", and the gap between those two sentences is where the bug report comes from.

Missing Number: the one that cannot break

Given n distinct values drawn from [0, n], XOR every index together with every value; identical pairs cancel and the absent one is left. The Gauss version subtracts the array sum from n(n+1)/2.

const missingNumberXor = (nums) => {
  let result = nums.length;
  for (let i = 0; i < nums.length; i++) result ^= i ^ nums[i];
  return result;
};
 
const missingNumberGauss = (nums) => {
  const n = nums.length;
  return (n * (n + 1)) / 2 - nums.reduce((s, x) => s + x, 0);
};
 
let cases = 0;
for (let n = 0; n <= 200; n++) {
  for (let miss = 0; miss <= n; miss++) {
    const nums = [];
    for (let v = 0; v <= n; v++) if (v !== miss) nums.push(v);
    for (let i = nums.length - 1; i > 0; i--) {
      const j = (i * 7919 + n * 31 + miss) % (i + 1);
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    cases++;
    assert(missingNumberXor(nums) === miss, `xor n=${n} miss=${miss}`);
    assert(missingNumberGauss(nums) === miss, `gauss n=${n} miss=${miss}`);
  }
}
for (let n = 201; n <= 4000; n++) {
  for (const miss of [0, n >> 1, n]) {
    const nums = [];
    for (let v = 0; v <= n; v++) if (v !== miss) nums.push(v);
    cases++;
    assert(missingNumberXor(nums) === miss, `xor n=${n} miss=${miss}`);
    assert(missingNumberGauss(nums) === miss, `gauss n=${n} miss=${miss}`);
  }
}
console.log(`missingNumber: ${cases} configurations, 0 failures`);

31,701 configurations, including n = 0 where the array is empty and the answer is 0, and both n = 1 cases. Neither approach fails, and neither can: the values are array indices, so they are bounded by array length, and Array tops out at 2^32 - 1 entries — you run out of memory decades before you run out of int32.

The Gauss formula has a different ceiling, and it is arithmetic rather than bitwise. n * (n + 1) / 2 is computed in float64, so it is exact only while the product stays inside the safe-integer range:

const gaussTerm = (n) => (n * (n + 1)) / 2;
const gaussExact = (n) => (BigInt(n) * BigInt(n + 1)) / 2n;
 
let firstInexact = null;
for (let n = 134217720; n < 134300000; n++) {
  if (BigInt(gaussTerm(n)) !== gaussExact(n)) { firstInexact = n; break; }
}
console.log("first inexact n:", firstInexact);         // 134217729
console.log("that is 2**27 + 1:", firstInexact === 2 ** 27 + 1);  // true
console.log(gaussTerm(firstInexact), String(gaussExact(firstInexact)));
// 9007199456067584 9007199456067585

2^27 + 1 elements is about 134 million, so this is theoretical. I include it because it is the only ceiling in the article that has nothing to do with 32-bit coercion, and knowing which ceiling you are standing on matters more than knowing that a ceiling exists.

Counting Bits: exact for every value I could enumerate

i >> 1 drops the low bit, so ans[i] = ans[i >> 1] + (i & 1). Each entry reuses one already-computed entry, which is what turns the O(n log n) per-number count into a single pass.

const countBitsDp = (n) => {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1);
  return dp;
};
 
const LIMIT = 1 << 20;
const table = countBitsDp(LIMIT);
let checked = 0;
for (let i = 0; i <= LIMIT; i++) {
  assert(table[i] === popcountRef(i), `dp[${i}] = ${table[i]}`);
  checked++;
}
console.log(`countBitsDp: ${checked} values verified against BigInt popcount`);
// countBitsDp: 1048577 values verified against BigInt popcount

All 1,048,577 entries match. This one is genuinely safe in practice for a reason worth naming: the thing being shifted is a loop index into an array you allocated, and dp[i >> 1] would read a negative index the moment i reached 2^31, which means you asked for a two-billion-element array and the allocation failed first.

Where each popcount loop stops being true

Three loops, all described the same way in most write-ups, all with different ceilings. I ran each over 0 .. 2^24 and then over two contiguous million-value blocks starting exactly at 2^31 and 2^32.

const popcountShiftSigned = (n) => {
  let c = 0;
  while (n > 0) { c += n & 1; n >>= 1; }
  return c;
};
 
const popcountShiftUnsigned = (n) => {
  let c = 0;
  while (n !== 0) { c += n & 1; n >>>= 1; }
  return c;
};
 
const popcountKernighan = (n) => {
  let c = 0;
  while (n !== 0) { n &= n - 1; c++; }
  return c;
};
 
const sweep = (label, fns, start, count) => {
  const wrong = fns.map(() => 0);
  for (let k = 0; k <= count; k++) {
    const v = start + k;
    const truth = popcountRef(v);
    fns.forEach((f, idx) => { if (f(v) !== truth) wrong[idx]++; });
  }
  console.log(label, "wrong out of", count + 1, ":", wrong.join(" / "));
};
 
const trio = [popcountShiftSigned, popcountShiftUnsigned, popcountKernighan];
sweep("0 .. 2^24         ", trio, 0, 1 << 24);
sweep("2^31 .. 2^31+2^20 ", trio, 2 ** 31, 1 << 20);
sweep("2^32 .. 2^32+2^20 ", trio, 2 ** 32, 1 << 20);
// 0 .. 2^24          wrong out of 16777217 : 0 / 0 / 0
// 2^31 .. 2^31+2^20  wrong out of 1048577 : 1048577 / 0 / 0
// 2^32 .. 2^32+2^20  wrong out of 1048577 : 1048577 / 1048577 / 1048576

Read the middle row. The while (n > 0) version is wrong for every single value in that block — not some, not the awkward ones, all 1,048,577 of them. 2147483648 >> 1 is -1073741824, the loop guard fails on the first check, and the function returns 0. A popcount of zero for a number with a bit set.

for (const v of [2 ** 31 - 1, 2 ** 31, 2 ** 31 + 1, 2 ** 32, 2 ** 32 + 1, Number.MAX_SAFE_INTEGER]) {
  console.log(v, [popcountShiftSigned(v), popcountShiftUnsigned(v), popcountKernighan(v)],
              "truth", popcountRef(v));
}
// 2147483647       [31, 31, 31]  truth 31
// 2147483648       [ 0,  1,  1]  truth 1
// 2147483649       [ 1,  2,  2]  truth 2
// 4294967296       [ 0,  0,  1]  truth 1
// 4294967297       [ 1,  1,  1]  truth 2
// 9007199254740991 [ 1, 32, 32]  truth 53

The bottom row is the summary of this entire section. Number.MAX_SAFE_INTEGER has 53 set bits. The signed-shift loop says 1. The other two say 32, which is not a coincidence and not a rounding error — it is the width of the register they were silently moved into. Any write-up that labels a popcount loop O(32) is describing the bug as if it were the complexity.

Kernighan's n & (n - 1) is the subtlest of the three, because it is almost right at the boundary. popcountKernighan(2 ** 32) returns 1, and 1 is correct, by accident — 2^32 coerces to 0 and the loop counts the one iteration it took to notice. One value up, at 2^32 + 1, n - 1 coerces to 0, the first & wipes everything, and you get 1 where the truth is 2. It is wrong for 1,048,576 of the 1,048,577 values in that block, and it is right for the one that makes you think it works.

On negatives it does terminate, which surprises people who have seen the same loop hang in C. -1 takes 32 iterations, -2147483648 takes one, and the reason is the coercion again: -2147483648 - 1 is -2147483649 as a Number, which & folds to 2147483647, and -2147483648 & 2147483647 is 0.

Every defect above is one traversal of that diagram. Step B is not an error condition, there is no warning, and the value that comes out of step E is a perfectly ordinary Number that will happily be compared, summed and printed.

If you want a popcount with no ceiling, you have to leave the 32-bit operators behind entirely, which means BigInt and roughly the shape of popcountRef at the top of this article. It is slower and it is correct for every integer you can represent, and in the places where popcount matters outside an interview — bitsets over more than 32 items, hash sketches, permission masks with more than 32 flags — that is the trade you want.

The power-of-two check is wrong for zero, and for two other values

n & (n - 1) === 0 gets quoted as the power-of-two test constantly, including by the version of this article I am replacing. It disagrees with the truth on 4 of the 4,211 values I checked.

const isPowerOfTwoNaive = (n) => (n & (n - 1)) === 0;
const isPowerOfTwoFixed = (n) => Number.isInteger(n) && n > 0 && (BigInt(n) & (BigInt(n) - 1n)) === 0n;
 
const disagree = [];
for (let n = -2100; n <= 2100; n++) {
  if (isPowerOfTwoNaive(n) !== isPowerOfTwoFixed(n)) disagree.push(n);
}
for (const n of [0, -2147483648, 2 ** 31, 2 ** 32, 2 ** 32 + 1, Number.MAX_SAFE_INTEGER]) {
  if (isPowerOfTwoNaive(n) !== isPowerOfTwoFixed(n)) disagree.push(n);
}
console.log("disagreements:", disagree);
// disagreements: [ 0, 0, -2147483648, 4294967297 ]

Zero is the one you will actually hit: 0 & -1 is 0, so the naive check calls zero a power of two. -2147483648 & 2147483647 is 0, so it calls the most negative int32 a power of two. And 4294967297 & 4294967296 becomes 1 & 0, so it calls 2^32 + 1 a power of two. The guard is n > 0 && in front, and if you are staying in int32 you can keep the fast form: n > 0 && (n & (n - 1)) === 0.

Adding without plus is addition modulo 2^32

XOR gives the sum ignoring carries, AND gives the positions where a carry happens, << 1 moves the carries one place left, repeat until there is nothing to carry.

const addWithoutPlus = (a, b) => {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
};
 
let pairs = 0;
for (let a = -512; a <= 512; a++) {
  for (let b = -512; b <= 512; b++) {
    assert(addWithoutPlus(a, b) === a + b, `${a} + ${b}`);
    pairs++;
  }
}
console.log(`addWithoutPlus: ${pairs} pairs, 0 failures`);   // 1050625 pairs, 0 failures
 
for (const [a, b] of [[2147483647, 1], [2147483647, 2147483647], [1e10, 1], [1.5, 2.5]]) {
  console.log(`${a} + ${b} -> ${addWithoutPlus(a, b)} (true ${a + b})`);
}
// 2147483647 + 1 -> -2147483648 (true 2147483648)
// 2147483647 + 2147483647 -> -2 (true 4294967294)
// 10000000000 + 1 -> 1410065409 (true 10000000001)
// 1.5 + 2.5 -> 3 (true 4)

All 1,050,625 pairs in [-512, 512] are exact, negatives included, and the loop always terminates — the carry eventually shifts off the top of the register and becomes 0, which is the same coercion that breaks the popcount loops, here doing exactly what a 32-bit adder is supposed to do. Outside int32 it wraps, silently, and it truncates fractions. That is not a bug in the trick; the trick is a 32-bit adder, and the only mistake is describing it as "add two integers".

Parity is the one that holds everywhere

Using x & 1 as a parity check survived everything I threw at it. 2,097,159 values across -2^20 .. 2^20 plus the safe-integer edges, zero disagreements with x % 2 !== 0:

let parityChecked = 0;
for (let x = -(1 << 20); x <= 1 << 20; x++) {
  assert((x & 1) === (x % 2 !== 0 ? 1 : 0), `parity ${x}`);
  parityChecked++;
}
for (const x of [2 ** 31, 2 ** 31 + 1, 2 ** 32, 2 ** 32 + 1, 2 ** 52 + 1, Number.MAX_SAFE_INTEGER]) {
  assert((x & 1) === (x % 2 !== 0 ? 1 : 0), `parity ${x}`);
  parityChecked++;
}
console.log(`x & 1: ${parityChecked} values, 0 disagreements`);
console.log(-3 & 1, -3 % 2);   // 1 -1

It holds because ToInt32 reduces modulo 2^32 and the low bit survives that reduction for every integer you can represent exactly, sign regardless. It is also the one place where & 1 is better than the arithmetic form rather than merely faster: -3 % 2 is -1 in JavaScript, so x % 2 === 1 misses every negative odd number, while -3 & 1 is 1.

Everything else on this page has a ceiling, and the only difference between the tricks that are safe in your codebase and the tricks that are waiting for you is whether you know which ceiling and how far below it you are standing.