In a 64 bit integer. I am trying to get the index of the leftmost non zero bit. I used the naive method of iterating over all the 64 bits to calculate this.
function getLowestBitPosition(bitstring) {
for (a = 0; a < bitstring.length; a++) if (bitstring[a] === "1") return a;
}
Similarly, I iterated backwards to get the index of the rightmost non zero bit.
function getHighestBitPosition(bitstring) {
for (a = bitstring.length - 1; a >= 0; a--) if (bitstring[a] === "1") return a;
}
I'm pretty sure that there is a more efficient way to implement this. I have seen methods in C requiring little iteration. However, all those examples are using C library functions. Is there a better way to get the index in javascript?
Realize the answer has already been selected for this question, but found it an interesting problem likely best solved with webassembly (WASM). Unfortunately, it appears that WASM does not support i64 parameters, so had to settle for sending the BigInt as lo / hi ( i32 / i32 ), and stitching together as an i64 within WASM before looking for the MSB.
EDIT Jan 2021: Per https://webassembly.org/roadmap/, the latest browsers are now supporting BigInt i64 parameters between javascript and WASM. This answer has been updated to now include the following WASM code lz64.wat compiled into lz64.wasm:
(module
(func $lz64 (param $val i64) (result i64)
get_local $val
i64.clz
)
(export "lz64" (func $lz64))
)
Compared with the WASM code below which needed to stitch together two i32 parameters, the code above is greatly simplified (and much faster)!
The WASM i32 code is fairly straightforward, leveraging https://pengowray.github.io/wasm-ops/ to determine the proper OpCodes. Additionally, used https://webassembly.github.io/wabt/demo/wat2wasm/ to create, debug, and compile the Web Assembly Text (WAT) to WASM. The i64.clz op is where the actual magic happens. All the code before that is to stitch the two i32 numbers together to form the actual i64 number to check. Note too that WASM acts a bit like an RPN calculator...
lz64v32.wat just below is compiled into 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))
)
The listing below includes the answer for the De Bruijn solution, in order to test the relative performance.
EDIT Also stumbled into What's the most efficient way of getting position of least significant bit of a number in javascript? which points out the Math.clz32 function(!). Put together a few help functions to support finding the MSB for a 64 bit BigInt, and ran tests with this third option also.
BEWARE! Running the code below will create 10M BigInts to run through the Math.clz32, WASM, and De Bruijn solutions. On my Acer laptop, on a handful of runs, the results are...
The WASM i64 solution is significantly faster!
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();BEWARE! Running this code will perform 40M tests, and there will be a pause before you see any results in the console log.