Published almost 4 years ago · Last edited 1 day ago · 5 min read

...and since they're so hard, I've decided to write them here as I learn.

Know some that are missing here? Let me know on twitter

isOdd implementation

Happens that you can check if a value is odd or not by shifting it 1 bit and checking if the result is 0 or 1.

In case the result is 0, then it means the given number is an odd number.

export const isOdd = (num: number) => Boolean(num & 0x01);

isPowerOfTwo implementation

A number is a power of 2 if it has exactly one bit set in its binary representation. For example: 2 (10), 4 (100), 8 (1000), 16 (10000).

The trick: if you subtract 1 from a power of 2, all bits flip. So n & (n - 1) will be 0 if n is a power of 2 (and n > 0).

export const isPowerOfTwo = (num: number) => num > 0 && (num & (num - 1)) === 0;

Round up to the next power of 2

Hash tables, memory allocators (jemalloc, SQLite's MEMSYS5), and GPU texture atlases all need sizes that are powers of 2. Once a size is a power of 2, modulo becomes a cheap bitwise AND: hash & (size - 1) instead of hash % size.

The trick is to "smear" the most significant bit downward with OR-shifts until all lower bits are 1, then increment. This is completely branchless.

export const roundUpToPowerOf2 = (v: number): number => {
  v--;
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  return v + 1;
};

Count set bits — Brian Kernighan's algorithm

Every time you compute n & (n - 1), the lowest set bit is cleared. Loop until n is 0 and count the iterations. This is O(k) where k is the number of set bits — far faster than checking all 32 bits one by one when bits are sparse.

GCC exposed this as __builtin_popcount() in 2003. It made it into the C++20 standard as std::popcount, the Linux kernel uses it for bitmap operations, and every chess engine uses it to count pieces on a bitboard.

export const countSetBits = (n: number): number => {
  let count = 0;
  while (n > 0) {
    n &= n - 1; // clear the lowest set bit
    count++;
  }
  return count;
};

Isolate the lowest set bit

n & -n returns a number with only the lowest set bit of n kept. It works because negation (two's complement) flips all bits then adds 1, which carries exactly up to the lowest set bit, aligning it perfectly with the original.

Chess engines use this constantly to pick off piece positions one at a time from a bitboard. Pair it with Brian Kernighan's trick above to iterate only over set bit positions in O(k).

export const lowestSetBit = (n: number): number => n & -n;

// Iterate over the positions of all set bits
export const iterateSetBits = (n: number): number[] => {
  const positions: number[] = [];
  while (n > 0) {
    positions.push(Math.log2(n & -n));
    n &= n - 1;
  }
  return positions;
};

Branchless absolute value

Modern CPUs pipeline instructions — they speculatively fetch the next instruction before the current one finishes. A mispredicted branch forces a pipeline flush worth ~15 cycles. In tight inner loops (audio codecs, physics engines, HFT), removing branches matters.

An arithmetic right-shift by 31 on a signed 32-bit integer fills all bits with the sign bit: n >> 31 is -1 (all 1s) for negatives and 0 for positives. XOR with -1 flips all bits; subtracting -1 adds 1 — that's exactly two's complement negation, with no conditional jump anywhere.

export const branchlessAbs = (n: number): number => {
  const mask = n >> 31; // -1 if negative, 0 if positive
  return (n ^ mask) - mask;
};

Fast inverse square root — the 0x5F3759DF trick

Quake III Arena (1999) needed to normalize millions of 3D vectors per frame for lighting calculations. Normalization requires 1 / √x, which was devastatingly slow on 1999 hardware. id Software's solution became one of the most studied hacks in computing history.

The insight: in IEEE 754 float representation, the raw bits are roughly proportional to the logarithm of the value. Right-shifting those bits by 1 halves the exponent — approximately taking a square root in log-space. Subtracting from the magic constant 0x5F3759DF flips the sign of the exponent — approximately taking the reciprocal. One Newton-Raphson iteration then polishes the approximation to within ~0.2% error. In JavaScript, DataView bridges the float↔integer boundary that C does with a pointer cast.

export const fastInverseSqrt = (x: number): number => {
  const buf = new ArrayBuffer(4);
  const view = new DataView(buf);
  view.setFloat32(0, x);
  let i = view.getUint32(0);
  i = 0x5f3759df - (i >> 1);
  view.setUint32(0, i);
  let y = view.getFloat32(0);
  // Newton-Raphson refinement
  y = y * (1.5 - 0.5 * x * y * y);
  return y;
};