algorithm - 计算整数中的尾随零最有效的方法是什么？

Question

正常的方式是

int main(){
  int a=2000,count=0,temp;
  while(a!=0)
  {
    temp=a%10;
    if(temp==0) count++
    else break;
    a/=10;
  }
  printf("%d",count);
}

有没有更高效的方法？

Answer 1

对于 32 位整数(最大值 2147483647)，您最多只需要进行 4 次测试。对于 64 位，再添加一个并测试 16 个零。

从 10 的较大次方开始并向下计算:

int countTrailingZeros(int n)
{
    int zeros = 0;
    if((n % 100000000) == 0)
    {
        zeros += 8;
        n /= 100000000;
    }
    if((n % 10000) == 0)
    {
        zeros += 4;
        n /= 10000;
    }
    if((n % 100) == 0)
    {
        zeros += 2;
        n /= 100;
    }
    if((n % 10) == 0)
    {
        zeros++;
    }
    return zeros;
}

这具有更好的最坏情况性能，但如果您传递的数字中有 9/10 没有尾随零，则平均情况会更糟。这仅取决于您在典型情况下传递给它的值。

但是，如果你传递给它的数字中有 9/10 没有尾随零，那么你可能不应该首先担心优化你的原始代码，因为它会在循环的第一次迭代中中断 90%时间。