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

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 位，再添加 1，并测试 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% 的情况下它会在循环的第一次迭代中中断。