Q:

How to find out how many bits are set (equal 1) in the product of two integers

I am looking for an algorithm solution to find out how many bits are set (equal 1)  if I multiply two integers. I have numbers A and B, between 0 and MAX_INT, to eliminate the negative numbers. How do I find out how many bits will be set in the product C = A * B.
-of course calculating C and counting the bits is not the correct solution, it won't work for high values
-I work in C and C++, but it is a rather general algorithm problem. I must solve it without any math/boost library help.
Tried finding a general solution to know the bit count, but what I guessed only worked for quite some examples, it entirely failed with high numbers.

A:

The question asks for an algorithm. The problem can be solved without holding a complete product, by computing each bit at a time, starting with bit 0.
Bit C0 is found from the product of A0 * B0 and is either 0 or 1.
Bit C1 is found from the sum of the products A0 * B1 + A1 * B0 and remembering any carry.
Bit C2 is found from the sum of carry + A0 * B2 + A1 * B1 + A2 * B0 and so on.
As you go, you sum the single product bits, which gives the required answer: number of set bits.

