How to find the number of set bits in large numbers ?

general
, , ,
1

By ‘Large’, I mean numbers containing up to 10^4 digits.
I have tried doing it by converting the number to binary, digit by digit (representing numbers as a vector of bits), so I multiply the current result by 10 and add the next digit, which I have done by adding two numbers, left shifted 3 times and 1 time(because N*10 = N<<3 + N<<1) and then wrote a function that adds two binary numbers represented this way, and then add the next digit. But its too slow.

1 Like
2

Is the number given in decimal representation?

1 Like
3

Yes, its given in decimal

4

You can simply find it in log(N) complexity by dividing it by 2 , But you have to do this operation in array representation of number

1 Like
5

@hemanth_1
well,I would love to do it in python as…
n=int(input())
b=bin(n)
ans=b.count(“1”)
print(ans)

Still u can find the way it could be done in c++…

2 Likes
6

The main task is to solve this question in standard way. Please don’t think that python will do anything.

1 Like
7

If I represent the number as an array, and say, it has ‘N’ digits, wouldn’t division by 2 take O(N) time ? and I’d have to do it Log 10^N times, which will roughly be the number of digits itself (correct me if I’m wrong).

8

__builtin_popcount()

There is a built in gcc function called __builtin_popcount()

which can calculate the set bits of a given number represented in decimal.

i.e

include <iostream>
using namespace std;

int main() {

cout  << __builtin_popcount(15);

return 0;

}

Output : 4

2 Likes
9

@bansal1232
Is __builtin_popcount an efficient way to do?

10

Have u frame this question by yourself? Or it is been given somewhere?

11

we are talking about 10^4 digits here

12

This was in a contest, I was not able to solve it

13

Got it accepted just now, it was slow because of the vector, I didn’t consider the fact that insertion at front is slow with it, used a deque instead and it got accepted :slight_smile: