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.

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

Is the number given in decimal representation?

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

@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++…

`__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

Yes, its given in decimal

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

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).

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

we are talking about 10^4 digits here

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

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