How many tailing zeros in a result of (long) multiplication

Question

I want to find out a number of tailing zeros in a result of multiplication there are.

My multiplication always gets out of long range and I found no other way other than use a bigint, but I want to avoid that for efficiency. Is there a faster way to find the trailing zero count of the product, without actually computing it in a BigInteger?

Answer 1

You don't need to multiply, multiplication (of the kind where two k-bit integers go in, and a 2k-bit integer comes out) usually has the property:

tzcnt(x * y) = tzcnt(x) + tzcnt(y)

This breaks down when x or y are zero, in that case the answer would be 2k regardless of how many trailing zeroes the other operand had.

So that leads to a simple algorithm:

1. if either input is zero, return 2k
2. otherwise, return tzcnt(x) + tzcnt(y)

This property comes from the way the partial products work: the lowest partial product (corresponding to the rightmost set bit in x) shifts y left by however many trailing zeroes x had, so this partial product has tzcnt(x) + tzcnt(y) trailing zeroes. Adding the other partial products never destroys this property since they are added at higher bit positions.