如何在JavaScript中使用基于表的方法找到8位，16位和32位整数的前导1 / 0 ?

在网上搜索了几个小时，但只找到以下内容。首先，JavaScript有Math.clz32(x)，所以你可以Count L heading Z在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位整数上的尾零似乎可以使用同一个表，尽管也许有更好的表用于这些?我想重用也很好。

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

所以问题中剩下的未解决的部分是:

如何使用"表方法"实现countLeadingZeroes32， 不使用使用BigInt(在JavaScript中)，而不诉诸于Math.clz32(x), Math.log等库函数?只有最基本的。
如何在JavaScript中使用表方法实现countLeadingZeroes[8/16](8位和16位)?
如何在JavaScript中使用表方法实现countLeadingOnes[8/16/32] ?

这是一个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。也就是说，通过使用优化的预计算表方法。

理想情况下，我们将有一个表生成函数的前导和尾表，但不是完全必要的这篇文章。除了预先计算的表，我什么也找不到，还没有生成它的算法。

从最初的问题中，我算出了1/0的计数:

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

尾零函数的表仅用于查找2的幂指数:-x & x返回2的幂，其尾零位数与x相同。这意味着您可以为前导零函数重用相同的查找表，因为它使用的技术在很大程度上是相同的;它"涂抹"后面的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];
}

最简单和非常脏的js解决方案可能是:

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

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

相关内容

最新更新

热门标签：