How to find the number of 1's in a binary representation of a number?

Question

From other searches, I found that this problem is called 'Hamming Weight' or 'Population Count'. There are lot of answers out there given with so many statistics? I need to find the solution in a simple way? Complexity is not a big deal. Is there any in-built function in JavaScript like Java's Integer.bitCount?

I'm currently doing this as follows.

var binary = 3;
var original = binary;
var count = 0;
while(binary>0)
{
    binary = binary >> 1 << 1;
    if(original-binary==1)
        count++;
    original = binary >> 1;
    binary = original;
}

Is there a better, more simple as well as elegant way for this?

If it's truly a string, `str.split('1').length`, but that's not javascript at all is it, it's Java — adeneo, Jul 01 '14 at 09:15
related to code review(http://codereview.stackexchange.com/questions) — Govind Singh, Jul 01 '14 at 09:18
@adeneo sorry wrong details. I need to perform this on a number. — Foreever, Jul 01 '14 at 09:19
Does the above methods have high time complexity? Which should I prefer? — Foreever, Jul 01 '14 at 09:23
Prefer over what, the code you've posted is not javascript, and you're asking for javascript, it's sorta hard to understand what you really want ? — adeneo, Jul 01 '14 at 09:23
@adeneo You are right. That wasn't JavaScript. What I'm wondering is that if the answer is this simple, why does everyone else suggest some complex methods to solve this? — Foreever, Jul 01 '14 at 09:30

Amarnath R Shenoy · Accepted Answer · 2014-07-01T10:17:21.347

6

try this

var binary = 10;
var result = binary.toString(2); //Converts to binary
var count = result.split(1);//  count -1 is your answer
alert((result.split('1').length-1));

can also be written as

(binary.toString(2).split('1').length-1)

toString(2)  : helps to split it in a base2 format which is binary, can do this in a range of 2- 36 (iam not sure about the range)

edited Jul 01 '14 at 10:17

answered Jul 01 '14 at 09:24

Amarnath R Shenoy

5,121
8
24
32

score 3 · Answer 2 · answered Apr 01 '17 at 04:41

3

If you want to count 1 digit in binary representation we can use regular expression like this.

number.toString(2).match(/1/g).length

answered Apr 01 '17 at 04:41

Duy Tran

39
1

score 2 · Answer 3 · answered Feb 27 '18 at 07:02

2

A simple way without using built-in functions:

function f(n){
    let i = 0;
    do if(n&1) ++i; while(n>>=1)
    return i;
}

// example:
console.log(f(7)); // 3

answered Feb 27 '18 at 07:02

A-Sharabiani

17,750
17
113
128

This seems to fail for large numbers (for example, `8224580541325813` should produce `28`, but this function produced `17`). This is because the right-shift operation will operate assuming your number is only a 32 bit number, and truncate anything beyond that. – Bronzdragon Apr 29 '23 at 17:56

Naveen Gupta · Answer 4 · 2022-08-04T09:55:18.543

1

  function numOfOnes(n) {
    if(n === 0) return n;
    return (n & 1) + numOfOnes(n >>= 1);
  }

Basically this approach belongs to recursive call.
It has the base condition when no number to evaluate.
Otherwise it calls itself on (n >>= 1) and add last digit (n & 1) to result.
eg. 7 has binary representation 111 = 1+1+1 = 3
17 has binary representation 10001 = 1+0+0+0+1 = 2

edited Aug 04 '22 at 09:55

answered Aug 03 '22 at 08:22

Naveen Gupta

306
3
11

Good answer, but an explanation of how and why it works would make this a great answer. – PhonicUK Aug 03 '22 at 16:33

score 0 · Answer 5 · answered Jul 31 '22 at 10:12

0

function countOnesInDecimal(num) {
  let count = 0;
  let binary = num.toString(2);
  const splitted = binary.split('');
  for (const iterator of splitted) {
    if (iterator === `1`) {
      count += 1;
    }
  }

  return count;
}
console.log(countOnesInDecimal(3));

answered Jul 31 '22 at 10:12

Anurag Sindhu

25
1
5

there is no need to split the string, you can just as easily iterate over a string instead of an array – BlobKat Nov 21 '22 at 16:45

How to find the number of 1's in a binary representation of a number?

5 Answers5

Linked