logo标签列表

高效确定整数位数的方法

c++integerdigits
169

在C++中，确定整数有多少位的非常高效的方法是什么？

14
以哪个进制呢？2进制？还是10进制？ - Jacob Krall
4
我想用十进制来做。 - Seth
1
我曾经问过一个相关的问题：如何获取int中的第一个数字？许多与下面相同的方法都被用在人们的答案中。如果这对你的任务有帮助，这是链接[https://dev59.com/pnRB5IYBdhLWcg3wJklC]。 - Dinah
1
虽然所有这些答案都是以十进制为基础的，但很容易更改以计算任何所需基数的结果。 - Ira Baxter
2
你对效率的衡量标准是什么？选项包括代码大小最小化、CPU周期数量、甚至结果的准确性。但每个选项都需要以不同的方式进行操作。而且，你指的是十进制数字、八进制数字、十六进制数字还是其他什么东西？ - Peter
显示剩余4条评论
33个回答
124

嗯，假设您知道整数的大小，最有效的方法是查找。这比基于对数的较短方法更快。如果您不关心计算“-”，请去掉+1。

#include <climits>

// generic solution
template <class T>
int numDigits(T number)
{
    int digits = 0;
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}

// partial specialization optimization for 64-bit numbers
template <>
int numDigits(int64_t x) {
    if (x == INT64_MIN) return 19 + 1;
    if (x < 0) return digits(-x) + 1;

    if (x >= 10000000000) {
        if (x >= 100000000000000) {
            if (x >= 10000000000000000) {
                if (x >= 100000000000000000) {
                    if (x >= 1000000000000000000)
                        return 19;
                    return 18;
                }
                return 17;
            }
            if (x >= 1000000000000000)
                return 16;
            return 15;
        } 
        if (x >= 1000000000000) {
            if (x >= 10000000000000)
                return 14;
            return 13;
        }
        if (x >= 100000000000)
            return 12;
        return 11;
    }
    if (x >= 100000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 1000000)
            return 7;
        return 6;
    }
    if (x >= 100) {
        if (x >= 1000) {
            if (x >= 10000)
                return 5;
            return 4;
        }
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial specialization optimization for 32-bit numbers
template<>
int numDigits(int32_t x)
{
    if (x == INT32_MIN) return 10 + 1;
    if (x < 0) return numDigits(-x) + 1;

    if (x >= 10000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 100000) {
            if (x >= 1000000)
                return 7;
            return 6;
        }
        return 5;
    }
    if (x >= 100) {
        if (x >= 1000)
            return 4;
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial-specialization optimization for 8-bit numbers
template <>
int numDigits(char n)
{
    // if you have the time, replace this with a static initialization to avoid
    // the initial overhead & unnecessary branch
    static char x[256] = {0};
    if (x[0] == 0) {
        for (char c = 1; c != 0; c++)
            x[c] = numDigits((int32_t)c);
        x[0] = 1;
    }
    return x[n];
}
5
可能比我的答案更快，干得好。为了增加效率，如果您知道输入的数字大多较小（我猜测小于100,000），则反转测试：如果（x < 10）返回1；如果（x < 100）返回2；等等，这样函数将进行较少的测试并更快地退出。 - squelart
35
或许你可以重新排序并嵌套if语句，实现二分查找而非线性查找。 - dave4420
1
这不是一个好主意。当架构扩展到256位整数时会发生什么？你需要记得回来修改这段代码。在现实生活中，这种情况不太可能发生，因为它可能用于构建正确大小的缓冲区，而现在你正在为更大的架构打开各种缓冲区溢出问题。 - Martin York
3
假设数字均匀分布，从最大位数开始进行反向线性搜索（从最高位到单位数），平均而言可能比二进制搜索更快，因为具有N位数的数字比具有N-1位数的数字要多得多。 - fa.
6
我不会过于担心256位或128位的整数。除非您需要计算宇宙中电子的数量（上次我计算是10^78），64位就足够了。32位机器持续了约15年。我猜测64位机器将持续更长时间。对于更大的数字，多精度算术将很好地解决问题，我怀疑计算数字数量的效率并不重要。 - Ira Baxter
显示剩余9条评论
85

最简单的方法是这样做：

unsigned GetNumberOfDigits (unsigned i)
{
    return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}

log10在<cmath>或<math.h>中定义。你需要对此进行分析以确定它是否比此处发布的其他任何方法都更快。我不确定它在浮点精度方面有多强大。此外，该参数是无符号的，因为负值和对数并不真正混合。

9
对于32位整数和56位浮点数，这个方法可能有效。如果输入是长整型（64位），双精度对数的56位可能会导致在接近10^n大值的情况下产生错误答案。建议在2^50以上的情况下使用时要小心。 - Ira Baxter
1
还有一个问题是对数函数的精度如何。我没有检查现代库中它们的准确性，也不会盲目地相信它们在十亿分之一的精度上是好的。 - David Thornley
@DavidThornley：日志或其他数学函数在编译器命令行上未指定时是完全精确的。有些将在编译时转换为x86内部函数，有些不存在并将扩展为现有内部函数的公式。例如，如果使用“-fpfast”，您可能会看到使用SSE内部函数而不是x87，这会对精度产生较少的保证（如果我没记错的话）。但默认情况下没有问题。 - v.oddou
@DavidThornley：这不仅仅是精度问题。问题在于是否保证对于所有相关的k，log10（10^k）≥ k。也就是说，任何不可避免的舍入误差是否保证朝着正确的方向。k + eps可以工作，而k - eps则不行。而“完美精确”是幼稚的想法。 - gnasher729
1
测试 i > 0 可以优化为 i > 9。 - Pat
77
也许我误解了问题，但这难道不是解决方法吗？
int NumDigits(int x)  
{  
    x = abs(x);  
    return (x < 10 ? 1 :   
        (x < 100 ? 2 :   
        (x < 1000 ? 3 :   
        (x < 10000 ? 4 :   
        (x < 100000 ? 5 :   
        (x < 1000000 ? 6 :   
        (x < 10000000 ? 7 :  
        (x < 100000000 ? 8 :  
        (x < 1000000000 ? 9 :  
        10)))))))));  
}
39
我不会感到惊讶，如果这个解决方案将是最快的。 - VisioN
@VisioN 看起来被接受的答案在 quick-bench 上快了约1.7倍，所以使用二叉树来减少比较似乎是有效的（如果输入在整个范围内均匀分布）。 - Ted Lyngmo
@TedLyngmo 可能是因为 x = abs(x) 在这里起到了额外的作用。 - VisioN
1
@VisioN 确实。被接受的答案中的函数对负数调用自身并添加 1。由于被测试的函数对负数没有做同样的事情，我删除了负数并在两个函数中使用了类型 std::uint_fast32_t。 - Ted Lyngmo
35
int digits = 0; while (number != 0) { number /= 10; digits++; }
注： "0" 将没有任何数字！如果你需要它显示一个数字，可以使用以下方法：
int digits = 0; do { number /= 10; digits++; } while (number != 0);

(感谢Kevin Fegan)

最终，使用性能分析器来确定这里所有答案中哪个在您的计算机上更快...

3
这种做法可能比我采用的展开循环方法快，但您需要对差异进行分析（从长远来看应该可以忽略不计）。 - Vitali
同意，性能分析是真正了解情况的唯一方法！我已经更新了我的回答，并加上了这个评论，因为Ben S的ceil(log10())答案已经消失了。 - squelart
14

将其转换为字符串，然后使用内置函数。

unsigned int i;
cout<< to_string(i).length()<<endl;
11

恶作剧：这是最高效的方法（数字的数量在编译时计算）：

template <unsigned long long N, size_t base=10>
struct numberlength
{
    enum { value = 1 + numberlength<N/base, base>::value };
};

template <size_t base>
struct numberlength<0, base>
{
    enum { value = 0 };
};

这可能有助于确定格式化，输入元素等所需的数字字段宽度。

6
首先，你的解决方案对于0无效。其次，你的解决方案不适用于变量的一般情况。第三，如果你正在使用一个常量字面量，那么你已经知道它有多少位数。 - Vitali
它也适用于0。 它还适用于任何基数。 其余的都是我已经概述的有效观点。 - blinnov.com
4
我认为它实际上并没有成功。它在数字“0”和基数“1”上失败了，并且如果给定的基数为“0”，则会出现除以零的错误。不过这个问题是可以解决的。总之，我只是在对一篇很旧的文章挑剔，所以抱歉，但我认为这可能并不是一个笑话，实际上可能很有用。 - tjm
我在这里提供了一个使用C++20编写的版本，可以与0一起使用。 - Vegeta
9

请参考《位操作技巧》，里面有一个更简短的答案，如果您的输入数据是正常分布的话，它还可以更快地找到答案，因为它首先检查大的常量。 (v >= 1000000000) 可以捕获 76% 的值，所以首先检查这个条件平均会更快。

不清楚位运算是否实际上更快。即使在最坏的情况下，我的修改方法也需要进行4次比较（如果进一步检查划分，可能能减少到3次，但似乎不太可能）。我严重怀疑算术操作+内存加载能够击败它（尽管如果访问足够多，这些操作会消失在CPU缓存中）。请记住，在他们给出的例子中，他们还将对数2隐含为某个抽象的IntegerLogBase2函数（该函数本身实际上并不便宜）。 - Vitali
仅作为跟进，如果数字是正态分布的话，进行顺序检查会更快。但是，在最坏情况下，它的退化情况会使速度变慢两倍。按数字位数而不是输入空间进行分区处理意味着行为没有退化情况，并且始终表现最佳。此外，请记住您正在做出假设，即数字将均匀分布。实际上，它们更可能遵循与<a href="http://en.wikipedia.org/wiki/Benford%27s_law">本福特定律</a>相关的某些分布，这是我的猜测。 - Vitali
位操作技巧并不比上面的分区方法更快，但如果您有一个更一般的情况，比如在这里使用浮点数，它们可能是有趣的。 - Corwin Joy
1
位操作技巧提供了一种获取int log10的方法，给定int log2。它提出了几种获取int log2的方法，大多涉及少量比较/分支。（我认为你低估了不可预测分支的成本，Vitali）。如果您可以使用内联x86汇编语言，则BSR指令将为您提供值的int log2（即最高有效位的位索引）。在K8上速度较慢（10个周期延迟），但在Core 2上速度很快（2或3个周期延迟）。即使在K8上，也可能比比较更快。 - Peter Cordes
在K10上，lzcnt计算前导零，因此它几乎与bsr相同，但输入为0不再是具有未定义结果的特殊情况。延迟：BSR：4，LZCNT：2。 - Peter Cordes
8
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
4
虽然这种方法在代码行数方面很高效，但是正如接受的答案所指出的，使用log可能不会提供最佳性能。 - Ian
1
@Ian 为什么不呢？这只需要几个 FPU 指令，比其他答案中所有的分支和循环都要好得多。 - user207421
7

之前的帖子建议使用除以10的循环。由于现代计算机上的乘法速度更快，我建议改用以下代码：

 int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
1
细节决定成败——比如说 std::numeric_limits<int>::max == number 会怎样？它可能无法正确终止。 - pgast
2
如果您担心这种情况，可以添加一个额外的IF来处理非常大的值。 - Ira Baxter
2
我应该指出，在x86计算机上，像这种情况中使用的乘以常数10实际上可以由编译器实现为LEA R2，[8 * R1 + R1]，ADD R1，R2，因此最多需要2个时钟。变量的乘法需要几十个时钟周期，而除法更糟。 - Ira Baxter
2
我对乘法方法（使用fabs来消除符号问题）和除法方法进行了基准测试。在我的机器上，除法方法比乘法方法慢了2倍。这是否为过早优化取决于调用的位置和方式。 - Spacemoose
@SpaceMoose: 用 fabs 进行2的因数计算？所以你是用浮点数进行基准测试的？我预期整数版本的运行速度会相对更快，因为硬编码的乘10应该比idiv更快。 - Ira Baxter
显示剩余2条评论
5

ppc架构具有位计数指令。使用它，您可以在单个指令中确定正整数的以2为底的对数。例如，32位将是：

#define log_2_32_ppc(x) (31-__cntlzw(x))

如果您可以处理大量数据的小误差，您可以使用另外几个指令将其转换为以10为底的对数：

#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))

这是平台特定的，略有不准确，但也不涉及分支、除法或转换为浮点数。一切取决于您的需求。

我只知道ppc指令，但其他架构应该有类似的指令。

这个解决方案计算log2(15)=4位和log2(9)=4位。但是，15和9需要不同数量的十进制数字才能打印。因此，它不起作用，除非您不介意有时数字打印出太多位数。但在这种情况下，您总可以选择“10”作为int的答案。 - Ira Baxter
哇，一个近似函数。不错。 - doug65536
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接