（长）乘法的结果中有多少尾随零

Question

我想找出乘法结果中尾零的个数

我的乘法总是超出 long 范围，除了使用 bigint 之外我没有找到其他方法，但为了效率我想避免这种情况。有没有更快的方法来查找产品的尾随零计数，而无需在 BigInteger 中实际计算它？

Answer 1

你不需要乘法，乘法（两个k位整数进去，2k位整数出来的那种）通常有属性:

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

当 x 或 y 为零时，这将失效，在这种情况下，无论其他操作数有多少尾随零，答案都是 2k。

所以这导致了一个简单的算法：

1. 如果任一输入为零，return 2k
2. 否则，return tzcnt(x) + tzcnt(y)

这 属性 来自部分积的工作方式：最低的部分积（对应于 x 中最右边的设置位）向左移动 y 不管有多少尾随零x 有，所以这个部分积有 tzcnt(x) + tzcnt(y) 个尾随零。添加其他部分产品永远不会破坏这个 属性 因为它们被添加在更高的位位置。