For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication

Question

I've recently stumbled upon a problem that I struggle realy hard with ever since.

There are two large decimal integers, order of magnitude $10^6$. The task is to find how many bits in the binary representation of $A*B$ are set (how many 1s are there in the binary representation). Now, for small numbers, that's trivial. You just multiply them, and then using bit-shifts compare each bit with a 1, incrementing a 1-counter every time bit & 1 is true. However, for very large numbers, hardly any programming language will allow the user to perform such multiplication. So how to achieve thet without any high-level languages and fancy libraries?

I think the proper start here is to create arrays for both numbers, to store them as separate digits. That can be done in a number of ways, from using sprintf and then transcribing the char array to int array using intarr[i] = chararr[i] - '0', or by a simple loop which divides the number modulo 10 and then divides it by 10. Either way, we're left with two arrays of the respective numbers' digits, and we can multiply them by each other quite easily. Now, we're left with and int array of the multiplication result's digits. Where do we go from here? How to get a binary representation of a very large number stored like that? How to count the 1s in its binary representation? Is there any trick for that?

Answer 1

I would assume that a very large product is at least say up to 128 bits (product of two 64 bit integers). In that case there are simple algorithms that calculate the higher and the lower 64 bits of the result, and then you count individually how many bits are set in the higher 64 bits, and how many in the lower 64 bits, and add the two numbers.

If your very large product is the product of say two numbers of $10^6$ bits each, these numbers could each be split into say 15,625 64 bit integers, and the product can be calculated easily with O(n^2) operations for n = 15,625. Or it can be calculated faster but with much more difficulty with a more complicated algorithm. This gives a result of 31,250 64 bit integers, and you can easily count the number of bits set in each integer, and add those numbers.