2

How to count the number of 1 bits in an integer.

So say you have the binary number 11100000. Basically there are 3 boolean flags at the beginning. The corresponding decimal notation for this is 224. Wondering how to take that integer and loop through it somehow to add the number of 1s that it starts with. Something like this:

var int = 224
var n = 8
var i = 0
var total = 0
while (i++ < n) {
  if (int.getBitAt(i) == 1) {
    total++
  } else {
    break
  }
}

I've never really dealt with bits so not sure how to accomplish this in an optimal way (i.e. without converting it to a string '11100000' or other unoptimal ways.

Lance
  • 75,200
  • 93
  • 289
  • 503
  • Your title and first sentence seems to conflict a bit with "number of 1s that it starts with". Can you clarify? Is your function input `11100000` or `224`? Thanks. – ggorlen Aug 24 '18 at 15:05
  • The input to the function would be 224. – Lance Aug 24 '18 at 15:05
  • Possible duplicate of [How to count the number of set bits in a 32-bit integer?](https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer) – whatsisname Aug 24 '18 at 16:16

4 Answers4

2

The easiest way to get such a thing is using bitwise operators. Basically:

var num = 224
var n = 8
var i = 0
var total = 0
while (i++ < n) {
  var mask = 1 << i
  if ( (mask & num) == (mask)) {
    total++
  }
}

Basically mask is a variable which is 1 at one place and 0 at all other places, like 0001000 with the high bit at i position.

mask & int is all zero if the i bit of int is 0, equal to mask if it is 1.

EDIT: I gave some tries on the console. First of all I got rid of the break, then I added some parenthes in the if statement. Probably some problems with the representation for the numbers made impossible for the statement to be true.

bracco23
  • 2,181
  • 10
  • 28
  • Hmm it's giving me 0. – Lance Aug 24 '18 at 15:10
  • @LancePollard This only counts the total number of bits from position 1 to 7. If you try it on 226 (11100010) you get 4, and if you try it on 225 (11100001) you get 3. If you want just the starting 0s this won't work – sbrass Aug 24 '18 at 15:28
  • @sbrass noted, thank you for checking. An approach like this, however, is closer to the ideal, with the bit-manipulation stuff. I need to learn how that masking stuff works. – Lance Aug 24 '18 at 15:30
  • @LancePollard I added another answer below using bit manipulation that should do what you need – sbrass Aug 24 '18 at 15:31
1

So here's another arbitrary bit length solution using bit twiddling:

function countBits(num){
    var idx=Math.floor(Math.log2(num)); //Get the number of bits needed to represent your number
    var bit=1;
    var count=0;
    while (bit){
        bit=(num & (1<<idx))>>idx; //Check the bit value in the given position
        count+=bit; //Add it to the count
        idx-=1; //Check the next bit over
    }
    return count;
}
sbrass
  • 905
  • 7
  • 12
  • That first line `idx` is tricky, not sure what the `Math.log2(num)` part is doing. – Lance Aug 24 '18 at 15:32
  • That's checking essentially how long the binary number will be. So for example, log2(224) is 7.8. That means you'll need 8 bits to represent it. So like 2^7 is 128 and 2^8 is 256. 8 is the smallest number of bits you can use to represent 224 then. – sbrass Aug 24 '18 at 15:34
0
const num = 42726; // value to count set bits in
const numBytes = 2; // number of bytes used to represent num
let i = 0;
let count = 0;
while (i < numBytes * 8) {
  if (((1 << i) & num) >> i === 1) count++;
  i++;
}
console.log(count); // 9
Famous Ketoma
  • 21
  • 2
-1

A way to do it for arbitrary bit length numbers could be something like:

function countBits(num){
    var s=num.toString(2); //Converts the number to a binary string
    if (s[0]==='0'){return 0;} //If the first digit is 0, return 0
    return s.split('0')[0].length; //Otherwise, return the number of 1s at the start
}
sbrass
  • 905
  • 7
  • 12