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.

Improve this question
3
  • 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. Commented Aug 24, 2018 at 15:05
  • The input to the function would be 224. Commented Aug 24, 2018 at 15:05
  • Possible duplicate of How to count the number of set bits in a 32-bit integer? Commented Aug 24, 2018 at 16:16

4 Answers 4

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Hmm it's giving me 0.
@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 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.
@LancePollard I added another answer below using bit manipulation that should do what you need
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;
}
Improve this answer

2 Comments

That first line idx is tricky, not sure what the Math.log2(num) part is doing.
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.
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
Improve this answer

Comments

-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
}
Improve this answer

2 Comments

I would prefer to do it using bit twiddling hacks :) thank you though!
what about handling 101, in this case its coming out to be counting 1 that is wrong.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.