Сколько хвостовых нулей в результате (длинного) умножения

Question

Я хочу узнать количество хвостовых нулей в результате умножения.

Мое умножение всегда выходит за пределы диапазона long, и я не нашел другого выхода, кроме использования bigint, но я хочу избежать этого для эффективности. Есть ли более быстрый способ найти счетчик конечных нулей продукта, не вычисляя его в BigInteger?

Answer 1

Вам не нужно умножать, умножать (например, когда входят два k-битных целых числа и 2k-битное целое число) обычно имеет свойство:

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

Это ломается, когда x или y равны нулю, в этом случае ответом будет 2k независимо от того, сколько конечных нулей было у другого операнда.

Так что это приводит к простому алгоритму:

1. если любой из входов равен нулю, вернуть 2k
2. , в противном случае вернуть tzcnt(x) + tzcnt(y)

Это свойство исходит из того, как работают частичные продукты:самый младший частичный продукт (соответствующий крайнему правому установленному биту в x) сдвигается y влево, как бы ни было много конечных нулей x, поэтому этот частичный продукт имеет tzcnt(x) + tzcnt(y) конечных нулей.Добавление других частичных продуктов никогда не разрушает это свойство, поскольку они добавляются в старших битовых позициях.