c++计算十进制数的位数

总结了计算十进制数的位数的几种方法

一

最常见一种方法就是不断地除以 10 直到为 0.

int GetDigitOfUInt1(uint32_t x) 
{
    int res = 0;
    while (x) {
        res += 1;
        x /= 10;
    }
    return res;
}

每次只除以 10 速度有点慢，可以优化一下每次除以100：

int GetDigitOfUInt2(uint32_t x) 
{
    int res = 0;
    while (x) {
        if (x < 10) {
            res += 1;
        } else {
            res += 2;
        }
        x /= 100;
    }
    return res;
}

二

第二种方法就是取对数

int GetDigitOfUInt3(uint32_t x) 
{
    if (x == 0) return 0;
    return 1 + (int)log10(x);
}

三

由于计算机取10的对数速度很慢，第二种方法速度比第一种慢很多，但是计算机取2的对数很快，只要进行移位操作就可以了，我们就可以通过 2 的对数来计算10的对数，第三种方法就是基于这个思想。

int GetDigitOfUInt4(uint32_t x)
{
    static const int  powers_of_10_u32[] = {
        0,
        10,
        100,
        1000,
        10000,
        100000,
        1000000,
        10000000,
        100000000,
        1000000000
    };
    uint32_t t = (32 - __builtin_clz(x | 1)) * 1233 >> 12;
    return t - (x < powers_of_10_u32[t]) + 1;
}

其中__builtin_clz是由gcc提供的计算一个数字前导 0 的个数的函数，(32 - __builtin_clz(x | 1)) 表示 $\log_2 x$的值. $\log_{10} x = \log_2 x / \log_2 10$,
$1/log_2 10 \approx 0.301$, $\frac{1233}{4096} \approx 0.301$.

最后比较一下运行时间：

#define TEST_FUCTION(func)                      \
    do {                                        \
        time_t t1, t2;                          \
        uint32_t maxNum = 200000000;            \
        t1 = GetCurrentMs();                    \
        for (uint32_t i = 0; i <= maxNum; ++i){ \
            func(i);                            \
        }                                       \
        t2 = GetCurrentMs();                    \
        std::cout << t2 - t1<<std::endl;        \
    }                                           \
    while (0);
    
int main()
{
    TEST_FUCTION(GetDigitOfUInt1)
    TEST_FUCTION(GetDigitOfUInt2)
    TEST_FUCTION(GetDigitOfUInt3)
    TEST_FUCTION(GetDigitOfUInt4)
}

输出：

3108    // 第一种，每次除以10
1920    // 第一种，每次除以100
6980    // 第二种
714     // 第三种

可以看出用log10计算的是最慢的，第三种方法最快，因为没有除法运算，除法运算是四种运算里最耗时的。

附录： gcc的一些__builtin_函数

__builtin_ffs(x)

返回x中最后一个为1的位是从后向前的第几位

__builtin_popcount(x)

x中1的个数

__builtin_ctz(x)

x末尾0的个数。x=0时结果未定义。

__builtin_clz(x)

x前导0的个数。x=0时结果未定义。

__builtin_parity(x)

x中1的奇偶性。

另外在这些函数名后面加 ll 就可以计算 long long类型对应的结果。

参考：

https://github.com/fmtlib/format-benchmark/blob/cbbe9a485c4a552548c5e2380caa00bad582410a/src/digits10/digits10.h (第三种方法)
https://blog.csdn.net/jasonchen_gbd/article/details/44948523

• 本文作者： JiXiaw
• 本文链接： http://jixiaw.github.io/2020/11/20/digitofnum/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！