javascript - 有效地获取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

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

---

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

(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/以确定正确的操作码。此外，使用过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 解决方案的答案，以测试相对性能。

编辑还偶然发现了What's the most efficient way of getting position of least significant bit of a number in javascript?它指出了 Math.clz32 函数(!)。将一些帮助函数放在一起以支持查找 64 位 BigInt 的 MSB，并使用第三个选项运行测试。

当心!运行下面的代码将创建 10M BigInt 来运行 Math.clz32、WASM 和 De Bruijn 解决方案。在我的宏碁笔记本电脑上，经过几次运行，结果是......

• Math.clz32 => 1.70s
• WASM i32 => 2.06 秒
• WASM i64 => 0.43 秒
• 德布鲁因 => 13.70 秒

WASM i64 解决方案速度明显更快!

var v232 = 2n ** 32n;

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

// https://stackoverflow.com/questions/61442006/whats-the-most-efficient-way-of-getting-position-of-least-significant-bit-of-a
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 测试，在控制台日志中看到任何结果之前会暂停。