Fast Way of Finding Most and Least Significant Bit Set in a 64-Bit Integer

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

How does clearing least significant bit repeatedly work in this algorithm?

c - 1 unsets the least significant bit in the binary representation of c and sets all the unset bits to the right of that bit.

When you binary and c - 1 with c you effectively unset all the bits to the right of the least significant set bit and also the least significant set bit. In other words the least significant set bit in c and everything to its right become zeros.

You count this as one, and rightly so. Because it was just one set bit fomr a ^ b.

Now, you continue this operation until c becomes zero and the number of operations is the number of set bits in c which is the number of different bits between a and b.

To give you an example for what c - 1 does to the binary representation of c:

c = 6, in binary 110
c-1 = 5, in binary 101
(c-1) & (c) = 110 & 101 = 100
The above is one iteration of the loop

Next iteration
c = 4, in binary 100
c-1 = 3, in binary 011
(c-1) & (c) = 100 & 101 = 0

The above successfully counts the number of set bits in 6.

This optimization helps you to improve the algorithm compared to when you right shift the number at each iteration and check whether the least significant bit is set. In the former case you operate in the number of positions where the most significant set bit is. Say for a power of 2 number, 2^7, you iterate 8 times until the number becomes zero. While with the optimized method you iterate according to the number of set bits. For 2^7 it would be just one iteration.

Related Topics