计算 64 位整数的位数

给定软件中的整数，您可能想知道它需要多少个小数位。例如，整数 100 需要 3 位数字，整数 9999 需要 4 位数字。

如果我们能够快速计算一个整数以 10 为底的对数，这将是一个简单的问题。不幸的是，我们的计算机以 2 为底工作，使用以 2 为底的对数速度更快。

有一些快速技术可以使用很少的指令来解决数字计数问题。对于 32 位整数，在 Hacker’s Delight 等参考文献中发现的经典技巧如下：

 int数字计数( uint32_t x ) { 静态uint32_t表[ ] = { 9 , 99 , 999 , 9999 , 99999 , 999999、9999999、99999999、999999999 } ；​​​​​​ int y = ( 9 * int_log2 ( x ) ) >> 5 ;  y + = x >表[ y ] ； 返回y + 1 ； }

其中 int_log2 函数只是计算以 2 为底的整数对数。以 2 为底，有一些快速函数可以计算对数……如果您在 C 或 C++ 中的 Clang 上使用 GCC，则可能会执行以下操作：

 int int_log2 ( uint64_t x ) { return 63 - __builtin_clzll ( x | 1 ) ; } 

请注意，我计算输入与整数 1 的按位或：我想避免计算零的对数。

有一个更快的功能， 我将其归功于 Willets ：

 int Alternative_digit_count ( uint32_t x ) { 静态uint64_t表[ ] = { 4294967296、8589934582、8589934582、8589934582、12884901788 、​​​​​​​​ 12884901788、12884901788、17179868184、17179868184、17179868184 、​​​​​​​​ 21474826480 、 21474826480 、 21474826480 、 21474826480 、 25769703776 、 25769703776 , 25769703776 , 30063771072 , 30063771072 , 30063771072 , 34349738368、34349738368、34349738368、34349738368、38554705664 、​​​​​​​​ 38554705664、38554705664、41949672960、41949672960、41949672960 、​​​​​​​​ 42949672960 , 42949672960 } ; 返回( x +表[ int_log2 ( x ) ] ) >> 32 ; }

如果您有 64 位整数而不是 32 位整数怎么办？

您可以推广相同的功能。首先我们有常规的fast函数：

 int数字计数( uint64_t x ) { 静态uint64_t表[ ] = { 9 , 99 , 999 , 9999 , 99999 , 999999 , 9999999 , 99999999 , 999999999 , 9999999999 , 99999999999 , 999999999999 , 9999999999999 , 99999999999999 , 999999999999999 UL , 9999999999999999 UL , 99999999999999999 UL , 999999999999999999 UL , 9999999999999999999 ULL } ; int y = ( 19 * int_log2 ( x ) >> 6 ) ;  y + = x >表[ y ] ； 返回y + 1 ； }

然后我们可以将更快的替代方案移植到 64 位整数，用 128 位查找表替换 64 位查找表：

 int Alternative_digit_count ( uint64_t x ) { 静态uint64_t表[ 64 ] [ 2 ] = { { 0x01 , 0xffffffffffffffff6 ULL } , { 0x01 , 0xffffffffffffffff6 ULL } , { 0x01 , 0xffffffffffffffff6 ULL } , { 0x01 , 0xffffffffffffffff6 ULL } , { 0x02 , 0xffffffffffffff9c ULL } , { 0x02 , 0xffffffffffffff9c ULL } , { 0x02 , 0xffffffffffffff9c ULL } , { 0x03 , 0xffffffffffffffc18 ULL } , { 0x03 , 0xffffffffffffffc18 ULL } , { 0x03 , 0xffffffffffffffc18 ULL } , { 0x04 , 0xffffffffffffd8f0 ULL } , { 0x04 , 0xffffffffffffd8f0 ULL } , { 0x04 , 0xffffffffffffd8f0 ULL } , { 0x04 , 0xffffffffffffd8f0 ULL } , { 0x05 , 0xfffffffffffe7960 ULL } , { 0x05 , 0xfffffffffffe7960 ULL } , { 0x05 , 0xfffffffffffe7960 ULL } , { 0x06 , 0xfffffffffff0bdc0 ULL } , { 0x06 , 0xfffffffffff0bdc0 ULL } , { 0x06 , 0xfffffffffff0bdc0 ULL } , { 0x07 , 0xffffffffff676980 ULL } , { 0x07 , 0xffffffffff676980 ULL } , { 0x07 , 0xffffffffff676980 ULL } , { 0x07 , 0xffffffffff676980 ULL } , { 0x08 , 0xfffffffffa0a1f00 ULL } , { 0x08 , 0xfffffffffa0a1f00 ULL } , { 0x08 , 0xfffffffffa0a1f00 ULL } , { 0x09 , 0xffffffffc4653600 ULL } , { 0x09 , 0xffffffffc4653600 ULL } , { 0x09 , 0xffffffffc4653600 ULL } , { 0x0a , 0xfffffffdabf41c00 ULL } , { 0x0a , 0xfffffffdabf41c00 ULL } , { 0x0a , 0xfffffffdabf41c00 ULL } , { 0x0a , 0xfffffffdabf41c00 ULL } , { 0x0b , 0xffffffe8b7891800 ULL } , { 0x0b , 0xffffffe8b7891800 ULL } , { 0x0b , 0xffffffe8b7891800 ULL } , { 0x0c , 0xffffff172b5af000 ULL } , { 0x0c , 0xffffff172b5af000 ULL } , { 0x0c , 0xffffff172b5af000 ULL } , { 0x0d , 0xfffff6e7b18d6000 ULL } , { 0x0d , 0xfffff6e7b18d6000 ULL } , { 0x0d , 0xfffff6e7b18d6000 ULL } , { 0x0d , 0xfffff6e7b18d6000 ULL } , { 0x0e , 0xffffa50cef85c000 ULL } , { 0x0e , 0xffffa50cef85c000 ULL } , { 0x0e , 0xffffa50cef85c000 ULL } , { 0x0f , 0xfffc72815b398000 ULL } , { 0x0f , 0xfffc72815b398000 ULL } , { 0x0f , 0xfffc72815b398000 ULL } , { 0x10 , 0xffdc790d903f0000 ULL } , { 0x10 , 0xffdc790d903f0000 ULL } , { 0x10 , 0xffdc790d903f0000 ULL } , { 0x10 , 0xffdc790d903f0000 ULL } , { 0x11 , 0xfe9cba87a2760000 ULL } , { 0x11 , 0xfe9cba87a2760000 ULL } , { 0x11 , 0xfe9cba87a2760000 ULL } , { 0x12 , 0xf21f494c589c0000 ULL } , { 0x12 , 0xf21f494c589c0000 ULL } , { 0x12 , 0xf21f494c589c0000 ULL } , { 0x13 , 0x7538dcfb76180000 ULL } , { 0x13 , 0x7538dcfb76180000 ULL } , { 0x13 , 0x7538dcfb76180000 ULL } , { 0x13 , 0x7538dcfb76180000 ULL } , } ; int log = int_log2 ( x ) ; uint64_t low =表[ log ] [ 1 ] ; uint64_t high =表[ log ] [ 0 ] ; 返回( x +低< x ) +高; } 

虽然我的 64 位代码可能看起来很神秘，但它所做的事情与原始 32 位函数相同：它将输入添加到查找值中，并保留最高有效位。

也许可以显着改进我的方法，但它是正确的。

我们想知道哪些函数速度快？

为了测试它，我概括了数千个随机整数，然后将它们的位数相加。我记录每个整数的指令数：

在 32 位情况下，替代方法可以为每个整数节省 3 或 4 条指令。但在 64 位情况下，节省的似乎只是一条指令，这并不一定值得。

接下来，让我们报告每个整数的 CPU 周期数。我运行了四次测试，其中一次测试出现了一些变化（Apple 平台，32 位替代）。

我的时间安排表明，传统的（和更简单的方法）可能会使用更多的指令，但在实践中仍然更可取。在 64 位情况下尤其如此，在我的测试中，替代方法要复杂得多，而且速度要慢得多。

我的代码可以在 GitHub 上找到。

原文： https://lemire.me/blog/2025/01/07/counting-the-digits-of-64-bit-integers/