How to find leading ones/zeroes for 8-bit, 16-bit, and 32-bit integers in JavaScript, using a table-based approach?

Question

Searched for a few hours on the web for this one, but only found the following. First, JavaScript has Math.clz32(x), so you can Count Leading Zeroes on the 32-bit value. That is all fine and well, but I want to know how these are implemented.

const trailingZeroesTable = [
  32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30,
  28, 11, 0, 13, 4, 7,
  17, 0, 25, 22, 31, 15,
  29, 10, 12, 6, 0, 21,
  14, 9, 5, 20, 8, 19, 18
];

const leadingZeroesTable = [
  31, 22, 30, 21, 18, 10, 29, 2,
  20, 17, 15, 13, 9, 6, 28, 1,
  23, 19, 11, 3, 16, 14, 7, 24,
  12, 4, 8, 25, 5, 26, 27, 0
]

function countTrailingZeroes32(x) {
  // Only difference between
  // (x and -x) is the value
  // of signed magnitude
  // (leftmostbit) negative
  // numbers signed bit is 1
  return trailingZeroesTable[(-x & x) % 37];
}

function countLeadingZeroes32(x) {
  x |= x >> 1n;
  x |= x >> 2n;
  x |= x >> 4n;
  x |= x >> 8n;
  x |= x >> 16n;
  return leadingZeroesTable[((x * 0x07c4acddn) & 0xffffffffn) >> 27n];
}

console.log('countLeadingZeroes32', countLeadingZeroes32(0b00000011000011110000111100001111n))
console.log('countTrailingZeroes32', countTrailingZeroes32(0b00000011000011110000110000000000))

Counting trailing zeroes on 16-bit and 8-bit integers appears to be able to use the same table, though perhaps there is a better table for these? I guess reuse is good too.

const trailingZeroesTable = [
  32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30,
  28, 11, 0, 13, 4, 7,
  17, 0, 25, 22, 31, 15,
  29, 10, 12, 6, 0, 21,
  14, 9, 5, 20, 8, 19, 18
];

function countTrailingZeroes32(x) {
  // Only difference between
  // (x and -x) is the value
  // of signed magnitude
  // (leftmostbit) negative
  // numbers signed bit is 1
  return trailingZeroesTable[(-x & x) % 37];
}

function countTrailingZeroes16(x) {
  return countTrailingZeroes32(x)
}

function countTrailingZeroes8(x) {
  return countTrailingZeroes32(x)
}

console.log('countTrailingZeroes32', countTrailingZeroes32(0b00000011000011110000110000000000))
console.log('countTrailingZeroes16', countTrailingZeroes16(0b0000001100001100))
console.log('countTrailingZeroes8', countTrailingZeroes8(0b00100000))

So the remaining unsolved bits parts of the question are:

1. How to implement countLeadingZeroes32 using the "table approach", without using BigInt (in JavaScript), and without resorting to library functions like Math.clz32(x), Math.log, etc.? Only bare basics.
2. How to implement countLeadingZeroes[8/16] (8-bit and 16-bit) in JavaScript using the table approach?
3. How to implement countLeadingOnes[8/16/32] in JavaScript using the table approach?

Here is a countTrailingOnes, which appears to just do countTrailingZeroes(~x), so that seems to work:

const trailingZeroesTable = [
  32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30,
  28, 11, 0, 13, 4, 7,
  17, 0, 25, 22, 31, 15,
  29, 10, 12, 6, 0, 21,
  14, 9, 5, 20, 8, 19, 18
]

function countTrailingZeroes32(x) {
  // Only difference between
  // (x and -x) is the value
  // of signed magnitude
  // (leftmostbit) negative
  // numbers signed bit is 1
  return trailingZeroesTable[(-x & x) % 37];
}

function countTrailingOnes32(x) {
  return countTrailingZeroes32(~x)
}

function countTrailingOnes16(x) {
  return countTrailingZeroes32(~x)
}

function countTrailingOnes8(x) {
  return countTrailingZeroes32(~x)
}

console.log('countTrailingOnes32', countTrailingOnes32(0b00000011000011110000110000011111))
console.log('countTrailingOnes16', countTrailingOnes16(0b0000001100001111))
console.log('countTrailingOnes8', countTrailingOnes8(0b00000011))

The main thing is, how to countLeadingZeroes[8/16/32] and countLeadingOnes[8/16/32] (which might just be countLeadingZeroes(~x)) in JavaScript, without using string hacks or BigInt. That is, by using an optimized precomputed table approach.

Ideally we would have a table-generating function for both the leading and trailing tables, but not totally necessary for this post. I couldn't find anything but the precomputed table, no algorithm for generating it yet.

From the original question, I figured out the count ones/zeroes:

const COUNT_BITS_TABLE = makeLookupTable()

function makeLookupTable() {
  const table = new Array(256).fill(0)
  // generate the lookup table
  for (let i = 0; i < 256; i++) {
    table[i] = (i & 1) + table[(i / 2) | 0];
  }
  return table
}

function countOneBits32(n) {
  return COUNT_BITS_TABLE[n & 0xff] +      // consider the first 8 bits
    COUNT_BITS_TABLE[(n >> 8) & 0xff] +       // consider the next 8 bits
    COUNT_BITS_TABLE[(n >> 16) & 0xff] +      // consider the next 8 bits
    COUNT_BITS_TABLE[(n >> 24) & 0xff];
}

function countOneBits16(n) {
  return COUNT_BITS_TABLE[n & 0xff] +      // consider the first 8 bits
    COUNT_BITS_TABLE[(n >> 8) & 0xff]
}

function countOneBits8(n) {
  return COUNT_BITS_TABLE[n & 0xff]
}

console.log('countOneBits32', countOneBits32(0b10101010000000001010101000000000))
console.log('countOneBits32', countOneBits32(0b10101011110000001010101000000000))
console.log('countOneBits16', countOneBits16(0b1010101000000000))
console.log('countOneBits8', countOneBits8(0b10000010))

Answer 1

The table for the trailing-zeroes function only exists to look up exponents for powers of two: -x & x returns the power of two with the same number of trailing zero bits as x. This means you can re-use the same look-up table for the leading-zeroes function, as the technique it uses is largely the same; it ‘smears’ trailing 1 bits to obtain a number with the same number of leading zero bits as the original input, and all bits that follow equal to 1. Incrementing that number gives you a power of two again.

function countLeadingZeroes32(x) {
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return 32 - trailingZeroesTable[((x + 1) & 0xffffffff) % 37];
}

Answer 2

Easiest and very dirty-JS solution would probably be:

function countLeadingZeroes32(x){
    return Math.max(0, 32-x.toString(2).length)
}

Which converts the number to a binary string and simply counts its length