在 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() and lastIndexOf() 会比 for 循环更快。

除此之外，我认为没有更快的方法可以在一串 1 和 0 中找到第一个设置位。

Answer 2

Ported/adapted 来自 this answer，这是从 BigInt 获取 MSB 或 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");

const
  b1 = BigInt(1),
  b2 = BigInt(2),
  b4 = BigInt(4),
  b8 = BigInt(8),
  b16 = BigInt(16),
  b32 = BigInt(32),
  b57 = BigInt(57);

function msb(v) {
  v |= v >> b1;
  v |= v >> b2;
  v |= v >> b4;
  v |= v >> b8;
  v |= v >> b16;
  v |= v >> b32;
  return deBruijn[
    BigInt.asUintN(
      64,
      (BigInt.asUintN(
        64,
        (v * multiplicator))) >> b57)
  ];
}

function lsb(v) {
  v = -v | v;
  return deBruijn[
    BigInt.asUintN(
      64,
      (BigInt.asUintN(
        64,
        (~(v) * multiplicator))) >> b57)
  ];
}
console.log(lsb(BigInt(18)))
console.log(msb(BigInt(18)))

Answer 3

意识到已经为这个问题选择了答案，但发现它是一个有趣的问题，可能最好用 webassembly (WASM) 来解决。不幸的是，WASM 似乎不支持 i64 参数，因此不得不将 BigInt 作为 lo / hi ( i32 / i32 ) 发送，并在寻找 MSB 之前在 WASM 中作为 i64 拼接在一起。

编辑 2021 年 1 月： 根据 https://webassembly.org/roadmap/，最新的浏览器现在支持 javascript 和 WASM 之间的 BigInt i64 参数。此答案已更新为现在包含以下 WASM 代码 lz64.wat 编译成 lz64.wasm:

(module
  (func $lz64 (param $val i64) (result i64)
    get_local $val
    i64.clz
  )
  (export "lz64" (func $lz64))
)

与下面需要拼接两个i32参数的WASM代码相比，上面的代码大大简化了（也快了很多）！

WASM i32 代码相当简单，利用 https://pengowray.github.io/wasm-ops/ to determine the proper OpCodes. Additionally, used https://webassembly.github.io/wabt/demo/wat2wasm/ 创建、调试 Web 程序集文本 (WAT) 并将其编译为 WASM。 i64.clz 操作是真正的魔法发生的地方。之前的所有代码都是将两个i32数字拼接在一起，形成实际的i64数字来检查。另请注意，WASM 的行为有点像 RPN 计算器...

下面的

lz64v32.wat编译成lz64v32.wasm

(module
  (func $lz (param $lo i32) (param $hi i32) (result i32)
    get_local $hi
    i64.extend_i32_u
    i64.const 32
    i64.shl
    
    get_local $lo
    i64.extend_i32_u
    i64.add
    
    i64.clz
    i32.wrap_i64
  )
  (export "lz" (func $lz))
)

下面的列表包括 De Bruijn 解决方案的答案，以测试相对性能。

EDIT 也无意中发现指出了 Math.clz32 函数（！）。将一些帮助函数放在一起以支持查找 64 位 BigInt 的 MSB，并且运行也使用第三个选项进行测试。

小心！运行下面的代码将通过 Math.clz32、WASM 和 De Bruijn 解决方案创建 10M BigInts 到运行。在我的 Acer 笔记本电脑上，在少数运行s 上，结果是...

Math.clz32 => 1.70s
WASM i32 => 2.06s
WASM i64 => 0.43s
De Bruijn => 13.70s

WASM i64 解决方案明显更快！

var v232 = 2n ** 32n;

function clz32(n) {
    return Math.clz32(n | 0);
}

// 
function ctz32(n) {
    n |= 0;
    return n ? 31 - Math.clz32(n & -n) : 0;
}

function clz64(bn) {
    let result = clz32(Number(bn / v232) | 0);
    if (result === 32) {
        result += clz32(Number(bn % v232) | 0);
    }
    return result;
}

function arrayBufferToBase64(arrayBuffer) {
    return btoa(String.fromCharCode(...new Uint8Array(arrayBuffer)));
}

function base64ToArrayBuffer(base64) {
    let s = atob(base64);
    let arrayBuffer = new ArrayBuffer(s.length);
    var bufferView = new Uint8Array(arrayBuffer);
    for (let i = 0; i < s.length; i++) {
        bufferView[i] = s.charCodeAt(i);
    }
    return arrayBuffer;
}

async function compile(fn, preCompiled) {
    let wasmBuffer;
    if (preCompiled) {
        wasmBuffer = base64ToArrayBuffer(preCompiled);
    } else {
        let response = await fetch(fn);
        wasmBuffer = await response.arrayBuffer();
        console.log(arrayBufferToBase64(wasmBuffer));
    }

    return await WebAssembly.instantiate(wasmBuffer);
}

async function runTest() {

    let wasm64v32 = await compile('./lz64v32.wasm', 'AGFzbQEAAAABBwFgAn9/AX8DAgEABwYBAmx6AAAKEAEOACABrUIghiAArXx5pwsAGQRuYW1lAQUBAAJsegILAQACAAJsbwECaGk=');
    let wasm64 = await compile('./lz64.wasm', 'AGFzbQEAAAABBgFgAX4BfgMCAQAHCAEEbHo2NAAACgcBBQAgAHkLABgEbmFtZQEHAQAEbHo2NAIIAQABAAN2YWw=');
    let v232 = 2n ** 32n;
    let randomBigInts = new Array(10000000);
    console.log(`Building ${randomBigInts.length.toLocaleString()} BigInts...\n\n`);
    for (let i = 0; i < randomBigInts.length; i++) {
        randomBigInts[i] = 2n ** BigInt(Math.round(Math.random() * 64));
    }

    console.log(`Math.clz32 MSB start check on ${randomBigInts.length.toLocaleString()} BigInts.`);
    randomBigInts.forEach(v=>{
        64 - clz64(v);
    });
    console.log('Done');

    let v = randomBigInts[0];
    console.log(`Math.clz32 test of msb ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${64 - clz64(v)}\n\n`);

    console.log(`WASM MSB start check on ${randomBigInts.length.toLocaleString()} BigInts via WASM, splitting 64 bit BigInt into 2 x i32 parameters.`);
    let lzf = wasm64v32.instance.exports.lz
    randomBigInts.forEach(v=>{
        64 - lzf(Number(v % v232), Number(v / v232));
    });
    console.log('Done');

    console.log(`WASM test of leading zeros ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${64 - lzf(Number(v % v232), Number(v / v232))}\n\n`);

    console.log(`WASM MSB start check on ${randomBigInts.length.toLocaleString()} BigInts via WASM using i64 parameter.`);
    let lzf64 = wasm64.instance.exports.lz64
    randomBigInts.forEach(v=>{
        64n - lzf64(v);
    });
    console.log('Done');

    console.log(`WASM test of leading zeros ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${64n - lzf64(v)}\n\n`);

    console.log(`DeBruijn MSB start check on ${randomBigInts.length.toLocaleString()} BigInts via deBruijn.`);
    randomBigInts.forEach(v=>{
        msb(v);
    });
    console.log('Done');
    console.log(`DeBruijn test of leading zeros ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${msb(v)}\n\n`);

}

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

const b1 = BigInt(1)
  , b2 = BigInt(2)
  , b4 = BigInt(4)
  , b8 = BigInt(8)
  , b16 = BigInt(16)
  , b32 = BigInt(32)
  , b57 = BigInt(57);

function msb(v) {
    v |= v >> b1;
    v |= v >> b2;
    v |= v >> b4;
    v |= v >> b8;
    v |= v >> b16;
    v |= v >> b32;
    return deBruijn[BigInt.asUintN(64, (BigInt.asUintN(64, (v * multiplicator))) >> b57)];
}

function lsb(v) {
    v = -v | v;
    return deBruijn[BigInt.asUintN(64, (BigInt.asUintN(64, (~(v) * multiplicator))) >> b57)];
}

runTest();

小心！运行此代码将执行 40M 测试，在控制台日志中看到任何结果之前会暂停。

在 javascript 中有效地获取最高和最低有效位

Efficiently getting most and least significant bit in javascript

javascript

bit-manipulation