如何使用基于 table 的方法在 JavaScript 中找到 8 位、16 位和 32 位整数的前导 ones/zeroes？

Question

在网上搜索了几个小时这个，但只找到了以下内容。首先，JavaScript有Math.clz32(x)，所以你可以C倒数L往Zeroes 在 32 位值上。一切都很好，但我想知道这些是如何实现的。

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))

计算 16 位和 8 位整数的尾随零似乎能够使用相同的 table，尽管也许有更好的 table？我想重用也很好。

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))

所以问题的剩余未解决部分是：

如何使用“table 方法”实现 countLeadingZeroes32， 不使用 使用 BigInt（在 JavaScript 中），并且不求助于 Math.clz32(x)、Math.log 等库函数？只有基本知识。
如何使用 table 方法在 JavaScript 中实现 countLeadingZeroes[8/16]（8 位和 16 位）？
如何使用 table 方法在 JavaScript 中实现 countLeadingOnes[8/16/32]？

Here 是一个 countTrailingOnes，它似乎只做 countTrailingZeroes(~x)，所以这似乎有效：

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))

主要是，如何在 JavaScript 中 countLeadingZeroes[8/16/32] 和 countLeadingOnes[8/16/32]（可能只是 countLeadingZeroes(~x)），而不使用字符串 hack 或 BigInt。也就是说，通过使用优化的预计算 table 方法。

理想情况下，我们将为前导和尾随 table 提供一个 table 生成函数，但对于此 post 并非完全必要。除了预先计算的 table，我什么都找不到，还没有生成它的算法。

从最初的问题，我算出了计数 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

trailing-zeroes 函数的 table 仅用于查找 2 的幂的指数：-x & x returns 具有相同尾数的 2 的幂零位为 x。这意味着您可以 re-use 与 look-up table 相同的 leading-zeroes 函数，因为它使用的技术基本相同；它“涂抹”尾随 1 位以获得与原始输入具有相同数量前导零位的数字，并且后面的所有位都等于 1。增加该数字再次得到 2 的幂。

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

最简单且非常 dirty-JS 的解决方案可能是：

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

它将数字转换为二进制字符串并简单地计算其长度

如何使用基于 table 的方法在 JavaScript 中找到 8 位、16 位和 32 位整数的前导 ones/zeroes？

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

javascript

bit-manipulation