c++ - 获得可整除整数的 10 的最大次方的高效算法

Question

我想找到能整除给定整数的 10 的最大次方。

我现在有一个简单的实现

int factorBase10Exp(int number){
//...
int mBase10Exp = 0;
while(number%10 == 0 && number != 0)
    {
        number /= 10; mBase10Exp++;
    }
//...
return mBase10Exp;
}

预期的输出是

factorBase10Exp(3000) = 3
factorBase10Exp(333) = 0

我不能将 std::log10 用作 log10(333) = 2.522，这会在我的用例中给出不正确的结果。

我可以做些什么来提高效率？

Answer 1

您可以使用一系列除法，每个除法的位数是前一个的一半。这为您提供了一种对零个数的二进制搜索。

if (number % 100000000 == 0)
{
    number /= 100000000;
    mBase10Exp += 8;
}
if (number % 10000 == 0)
{
    number /= 10000;
    mBase10Exp += 4;
}
if (number % 100 == 0)
{
    number /= 100;
    mBase10Exp += 2;
}
if (number % 10 == 0)
{
    number /= 10;
    mBase10Exp++;
}

第一个除法需要足够大，以覆盖整数 10 的最大幂的一半以上。