# Count set bits

Count the total number of set bits of multiplication of A and B. Range of A and B is up to 1000000000. Please help someone

10^9 is not so big. If 1\le A, B \le 10^9 then definitely 1\le A\times B \le 10^{18}. The product will fit in a long int. Then counting set bits is trivial - you just keep dividing it by 2 and track the number of times the \text{LSB} is set.

CPP Snippet
long long int a = 0, b = 0;
cin >> a >> b;
long long int product = a * b;
int set_bits = 0;
while(product) {
set_bits += (product & 1);
product >>= 1;
}
cout << set_bits << '\n';

1 Like

Yes, but it is not storing.

No of set bits in 2 is 1 and in 3 is 2 if you calculate the set bit of 6 is 2 then how can you say that sum of individuals are equal to multiple of them

Sorry, I misunderstood the question.

What do you mean by not storing?

1 Like