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?

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?

• javascript
• bit-manipulation

• There would have been Math.clz32 for use on 32 bit blocks, with strings there will always be iteration, whether you do it yourself or you call some built-in – user555045 Commented May 29, 2020 at 11:17
• For strings, the methods indexOf and lastIndexOf exist … – C3roe Commented May 29, 2020 at 11:19
• When you say a "64 bit integer", how does this work? JS numbers are IEEE-754 double-precision which allows for 53bits of precision. 64 bit int doesn't fit into this properly. – spender Commented May 29, 2020 at 11:19
• @spender One can use the BigInt function to store it – Crupeng Commented May 29, 2020 at 11:20
• Do you have access to the raw binary form of those integers? (i.e. from a binary file or buffer) – Danny_ds Commented May 29, 2020 at 11:27

4 Answers 4

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/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 piled 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 pile 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 piled 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...

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

The WASM i64 solution is significantly faster!

var v232 = 2n ** 32n;

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

// https://stackoverflow./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 pile(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 pile('./lz64v32.wasm', 'AGFzbQEAAAABBwFgAn9/AX8DAgEABwYBAmx6AAAKEAEOACABrUIghiAArXx5pwsAGQRuYW1lAQUBAAJsegILAQACAAJsbwECaGk=');
    let wasm64 = await pile('./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.

Ported/adapted from this answer, this is a nice, string-free, loop-free and conditional-free way for getting the MSB or LSB position from a BigInt.

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

Since you don't seem to have access to the raw binary form of those integers, but instead have to work on their bitstring representation, you will be limited to using string functions.

Most likely the built-in functions indexOf() and lastIndexOf() will be faster than a for-loop.

Other than that I don't think there is a faster way to find the first set bit in a string of ones and zeros.

Simple and efficient solution using bitwise operations on BigInts. To get the left most bit, it bit shifts the value to the right by one repeatedly and keeps a count of how many times it does before the value bees 1. For the right most bit, it uses a bitwise AND against a mask. It increases the mask by left shifting it by one, counting the iterations, until the AND operation is equals to the mask. I've included the power of 2 exponent and their actual integer values.

function getMostAndLeastSignificantBits(x){
  let y = BigInt(x);
  
  // Find most significant bit
  let kPosition = 1n; // Bit position
  let kValue = 1n; //Bit value (2^k)
  while(y > 1n){
    y = y >> 1n;
    kPosition = kPosition + 1n;
    kValue = kValue << 1n;
  }
  
  // Find least significant bit
  let mPosition = 1n; // Bit position
  let mValue = 1n;
  y = BigInt(x);
  
  while((y & mValue) != mValue){
    mValue = mValue << 1n;
    mPosition = mPosition + 1n;
  }
  
  console.log('Most significant bit', `2^${kPosition} =`, parseInt(kValue))
  console.log('Least significant bit', `2^${mPosition} =`, parseInt(mValue))

}

getMostAndLeastSignificantBits("0b11001110000011000011000000000") // 432113152 as bit string
getMostAndLeastSignificantBits(344) // 0b101011000 as integer