Efficiently count the number of bits in an integer in JavaScript

Question

Let's say I have an integer I and want to get the count of 1s in its binary form.

I am currently using the following code.

Number(i.toString(2).split("").sort().join("")).toString().length;

Is there a faster way to do this? I am thinking about using bitwise operators. Any thoughts?

NOTE: i is within the 32-bit limitation.

Answer 1

You can use a strategy from this collection of Bit Twiddling Hacks:

function bitCount (n) {
  n = n - ((n >> 1) & 0x55555555)
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}

console.log(bitCount(0xFF)) //=> 8

Note that the above strategy only works for 32-bit integers (a limitation of bitwise operators in JavaScript).

A more general approach for larger integers would involve counting 32-bit chunks individually (thanks to harold for the inspiration):

function bitCount (n) {
  var bits = 0
  while (n !== 0) {
    bits += bitCount32(n | 0)
    n /= 0x100000000
  }
  return bits
}

function bitCount32 (n) {
  n = n - ((n >> 1) & 0x55555555)
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}

console.log(bitCount(Math.pow(2, 53) - 1)) //=> 53

You could also use a regular expression:

function bitCount (n) {
  return n == 0 ? 0 : n.toString(2).match(/1/g).length
}

console.log(bitCount(0xFF)) //=> 8

Answer 2

A recursive very nice but slow way:

    function count1(n, accumulator=0) {
      if (n === 0) {
        return accumulator
      }
      return count1(n/2, accumulator+(n&1))
    }

console.log(count1(Number.MAX_SAFE_INTEGER));

But if you want a very fast one (faster than T.J. Crowder answer)):

    count1s=(n)=>n.toString(2).replace(/0/g,"").length

console.log(count1s(Number.MAX_SAFE_INTEGER));

Note: some of the other solutions do not work with bit integers (> 32 bit) these two do!

Now, if we consider only 32 bit numbers, the fastest way is this:

function bitCountBigInt (n) {
  n = BigInt(n)
  let bits = 0
  while (n !== 0n) {
    bits += Number(n & 1n)
    n >>= 1n
  }
  return bits
}
function count1s32(i) {
  var count = 0;
  i = i - ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  i = (i + (i >> 4)) & 0x0f0f0f0f;
  i = i + (i >> 8);
  i = i + (i >> 16);
  count += i & 0x3f;
  return count;
}

  console.log(count1s32(0xffffffff));

https://jsperf.com/count-1/1

53 bit comparison:

32 bit comparison:

Benchmark here! (since jsperf is often down).

function log(data) {
  document.getElementById("log").textContent += data + "\n";
}

benchmark = (() => {

  time_function = function(ms, f, num) {
    var z;
    var t = new Date().getTime();
    for (z = 0;
      ((new Date().getTime() - t) < ms); z++) f(num);
    return (z / ms)
  } // returns how many times the function was run in "ms" milliseconds.

  // two sequential loops
  count1s = (n) => n.toString(2).replace(/0/g, "").length

  // three loops and a function.
  count1j = (n) => n.toString(2).split('').filter(v => +v).length

  /*  Excluded from test because it's too slow :D
  
      function count1(n, accumulator=0) {
          if (n === 0) {
              return accumulator
          }
          return count1(n / 2, accumulator + (n & 1))
      }
  */

    function bitCountBigInt (n) {
      n = BigInt(n)
      let bits = 0
      while (n !== 0n) {
        bits += Number(n & 1n)
        n >>= 1n
      }
      return bits
    }
    
  function countOnes(i) {
    var str = i.toString(2);
    var n;
    var count = 0;
    for (n = 0; n < str.length; ++n) {
      if (str[n] === "1") {
        ++count;
      }
    }
    return count;
  } // two sequential loops ( one is the toString(2) )

  function count1sb(num) {
    i = Math.floor(num / 0x100000000);
    //      if (i > 0) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    count = i & 0x3f;
    i = num & 0xffffffff;
    //      }
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    count += i & 0x3f;
    return count;
  }

  function benchmark() {
    function compare(a, b) {
      if (a[1] > b[1]) {
        return -1;
      }
      if (a[1] < b[1]) {
        return 1;
      }
      return 0;
    }



    funcs = [
      [count1s, 0],
      [count1j, 0],
      [count1sb, 0],
      [countOnes, 0],
      [bitCountBigInt, 0]
    ];

    funcs.forEach((ff) => {
      console.log("Benchmarking: " + ff[0].name);
      ff[1] = time_function(2500, ff[0], Number.MAX_SAFE_INTEGER);
      console.log("Score: " + ff[1]);

    })
    return funcs.sort(compare);
  }

  return benchmark;
})()
log("Starting benchmark...\n");
res = benchmark();
console.log("Winner: " + res[0][0].name + " !!!");
count = 1;
res.forEach((r) => {
  log((count++) + ". " + r[0].name + " score: " + Math.floor(10000 * r[1] / res[0][1]) / 100 + ((count == 2) ? "% *winner*" : "% speed of winner.") + " (" + Math.round(r[1] * 100) / 100 + ")");
});
log("\nWinner code:\n");
log(res[0][0].toString());

<textarea cols=80 rows=30 id="log"></textarea>

The benchmark will run for 10s.

Answer 3

Or, take any of the above functions, generate an array with values for (0..255), (save the array) and do a lookup for each 8 bit group. For an n-bit number takes ceil((n-1)/8) shifts, ands and table lookups.

Answer 4

1. Regex

const bitCount = (n) => (n.toString(2).match(/1/g) || []).length;

2. Bitwise AND, Right Shift

    function bitCount(n) {
        let count = 0;
        while(n) {
            count += n & 1;
            n  >>= 1; 
        }
        return count;
    }

3. Brian Kernighan algorithm

    function bitCount(n) {
        let count = 0;
        while(n) {
            n &= (n-1); 
            count ++;
        }
        return count;
    }

test:

    bitCount(0) // 0
    bitCount(1) // 1
    bitCount(2) // 1
    bitCount(3) // 2

Answer 5

Simple solution if you just want to count number of bit!

const integer = Number.MAX_SAFE_INTEGER;
integer.toString(2).split("").reduce((acc,val)=>parseInt(acc)+parseInt(val),0);

Answer 6

Keeps on checking if last bit is 1, and then removing it. If it finds last bit is one, it adds it to its result.

Math.popcount = function (n) {
  let result = 0;

  while (n) {
    result += n % 2;
    n = n >>> 1;
  };

  return result;
};

console.log(Math.popcount(0b1010));

For 64 bits, you can represent the number as two integers, the first is the top 32 digits, and the second is the bottom 32. To count number of ones in 64 bits, you can seperate them into 2, 32 bit integers, and add the popcount of the first and second.

Answer 7

A few more "fun" 1-liners:

Recursive: count each bit recursively until there's no more bits set

let f = x => !x ? 0 : (x & 1) + f(x >>= 1);

Functional: split the base 2 string of x and return the accumulated length of bits set

g = x => x.toString(2).split('0').map(bits => bits.length).reduce((a, b) => a + b);

Answer 8

if you want to use an absolute one liner solution you can have a look at this.

countBits = n => n.toString(2).split('0').join('').length;

1.Here n.toString(2) converts n into binary string

2.split('0') makes array out of the binary string splitting only at 0's and hence returning an array of only 1 present in binary of n

3.join('') joins all one and making a string of 1s

4.length finds length of the string actually counting number of 1's in n.

Answer 9

Doing n = n & (n - 1) you removing last 1 bit in the number. According to this, you can use the following algorithm:

function getBitCount(n) {
  var tmp = n;
  var count = 0;
  while (tmp > 0) {
    tmp = tmp & (tmp - 1);
    count++;
  }
  return count;
}

console.log(getBitCount(Math.pow(2, 10) -1));

Answer 10

Below works fine with any number:

var i=8823475632,count=0;while (i=Math.floor(i)) i&1?count++:0,i/=2
console.log(count); //17

change the i to the value you want or wrap it as a function

if integer is within 32-bit , below works

var i=10,count=0;while (i) i&1?count++:0,i>>=1

Answer 11

Given that you're creating, sorting, and joining an array, if it's literally faster you want, you're probably better off doing it the boring way:

console.log(countOnes(8823475632));

function countOnes(i) {
  var str = i.toString(2);
  var n;
  var count = 0;
  for (n = 0; n < str.length; ++n) {
    if (str[n] === "1") {
      ++count;
    }
  }
  return count;
}

(Use str.charAt(n) instead of str[n] if you need to support obsolete browsers.)

It's not as l33t or concise, but I bet it's faster it's much faster:

...and similarly on Firefox, IE11 (IE11 to a lesser degree).

Answer 12

You can skip Number, sort and the second toString. Use filter to only consider the 1s (a truthy value) in the array then retrieve how many got through with length.

i.toString(2).split('').filter(v => +v).length