有效获取javascript中的最高有效位和最低有效位

Question

以64位整数表示。我正在尝试获取最左边的非零位的索引。我使用了对所有64位进行迭代的幼稚方法来进行计算。

function getLowestBitPosition(bitstring) {
    for (a = 0; a < bitstring.length; a++) if (bitstring[a] === "1") return a; 
}

类似地，我向后迭代以获取最右边的非零位的索引。

function getHighestBitPosition(bitstring) {
    for (a = bitstring.length - 1; a >= 0; a--) if (bitstring[a] === "1") return a; 
}

我非常确定，有一种更有效的方法来实现这一目标。我已经看到了C语言中需要很少迭代的方法。但是，所有这些示例都使用C库函数。有没有更好的方法来获取javascript中的索引？

Answer 1

由于您似乎无法访问这些整数的原始二进制形式，因此将只能使用字符串函数。

最有可能内置函数indexOf()和lastIndexOf()比for循环要快。

除此之外，我认为找不到字符串中第一个置位的更快方法。

Answer 2

从this answer移植，这是从BigInt获取LSB位置的一种不错的，无循环的方法。

const deBruijn = [
  0,
  48, -1, -1, 31, -1, 15, 51, -1, 63, 5, -1, -1, -1, 19, -1,
  23, 28, -1, -1, -1, 40, 36, 46, -1, 13, -1, -1, -1, 34, -1, 58, -1, 60, 2, 43, 55, -1, -1, -1, 50, 62, 4, -1, 18, 27, -1, 39,
  45, -1, -1, 33, 57, -1, 1, 54, -1, 49, -1, 17, -1, -1, 32, -1,
  53, -1, 16, -1, -1, 52, -1, -1, -1, 64, 6, 7, 8, -1, 9, -1, -1, -1, 20, 10, -1, -1, 24, -1, 29, -1, -1, 21, -1, 11, -1, -1,
  41, -1, 25, 37, -1, 47, -1, 30, 14, -1, -1, -1, -1, 22, -1, -1,
  35, 12, -1, -1, -1, 59, 42, -1, -1, 61, 3, 26, 38, 44, -1, 56
];
const multiplicator = BigInt("0x6c04f118e9966f6b");

function bitSize(v) {
  v |= v >> BigInt(1);
  v |= v >> BigInt(2);
  v |= v >> BigInt(4);
  v |= v >> BigInt(8);
  v |= v >> BigInt(16);
  v |= v >> BigInt(32);
  return deBruijn[BigInt.asUintN(64, (BigInt.asUintN(64, (v * multiplicator))) >> BigInt(57))];
}
console.log(bitSize(BigInt(16)))