计算整数的十进制长度的最快方法是什么?(.net)

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (25)

我有一些代码可以做很多64位整数的比较,但是它必须考虑数字的长度,就好像它被格式化为一个字符串一样。我不能改变调用代码,只能改变函数。

最简单的方法(除了.ToString()。Length)是:

(int)Math.Truncate(Math.Log10(x)) + 1;

但是,表现相当差。由于我的应用程序只发送正值,并且长度在2到9之间均匀分布(有些偏向9),所以我预先计算了值并且有if语句:

static int getLen(long x) {
    if (x < 1000000) {
        if (x < 100) return 2;
        if (x < 1000) return 3;
        if (x < 10000) return 4;
        if (x < 100000) return 5;
        return 6;
    } else {
        if (x < 10000000) return 7;
        if (x < 100000000) return 8;
        if (x < 1000000000) return 9; 
        return (int)Math.Truncate(Math.Log10(x)) + 1; // Very uncommon
    }
}

这使得长度可以与平均4比较来计算。

那么,有没有其他的技巧可以使这个功能更快?

这将作为32位代码(Silverlight)运行。

提问于
用户回答回答于

两点建议:

  1. 简介并将常见病例列入首位。
  2. 在最坏的情况下进行二分搜索以最小化比较的数量。可以使用正确的三个比较来决定8个备选方案。

除非分布非常歪斜,否则这种组合可能不会给你带来太多的收益。

用户回答回答于

查找整数的整数记录10

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;          // result goes here
int t;          // temporary

static unsigned int const PowersOf10[] = 
    {1, 10, 100, 1000, 10000, 100000,
     1000000, 10000000, 100000000, 1000000000};

t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above)
r = t - (v < PowersOf10[t]);

通过首先使用上述技术之一来计算整数对数基10,以找到对数基2.通过关系log10(v)= log2(v)/ log2(10),我们需要将它乘以1 / log2( 10),大约是1233/4096,或1233,然后是右移12。因为IntegerLogBase2向下舍入,所以需要添加一个。最后,由于值t只是一个近似值,所以可以通过减去v <PowersOf10 [t]的结果找到确切的值。 此方法比IntegerLogBase2多6个操作。它可以通过修改上面的日志基2表查找方法来加速(在具有快速内存访问权的机器上),以便条目保存t的计算值(即,预先添加,-mulitply和-shift)。这样做只需要9次操作即可找到日志库10,假设使用了4个表(每个字节对应一个表)。

就计算IntegerLogBase2而言,该页面上提供了几个替代方案。这是各种高度优化的整数运算的很好的参考。

你的版本的一个变种也是存在的,除了它假设值(而不是值的对数基数)是均匀分布的,因此它是按指数顺序搜索的:

以显而易见的方式查找整型日志基数为10的整数

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;          // result goes here

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : 
    (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : 
    (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0;

当输入均匀分布在32位值上时,此方法运行良好,因为76%的输入被第一次比较捕获,21%被第二次比较捕获,2%被第三次捕获,等等(斩波其余各项比较下降了90%)。结果,平均需要少于2.6次的操作。

扫码关注云+社区