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