计算整数小数长度的最快方法？(.净)

Question

我有一些代码可以对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)运行.

更新:

我采纳了Norman的建议并且稍微改变了ifs,导致平均只有3个比较.根据Sean的评论,我删除了Math.Truncate.总之,这促进了大约10%的事情.谢谢!

Answer 1

两个建议:

1. 简介并将常见案例放在第一位.
2. 进行二分查找以最小化最坏情况下的比较次数.您可以使用恰好三个比较来决定8个替代方案.

除非分布非常偏斜,否则这种组合可能不会给你带来太大的影响.

Answer 2

来自Sean Anderson的Bit Twiddling Hacks:

查找整数的整数对数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]);

通过首先使用上述技术之一来查找日志库2来计算整数对数库10.通过关系log10(v)= log2(v)/ log2(10),我们需要将其乘以1/log2( 10),大约是1233/4096,或1233,然后右移12.需要添加一个,因为IntegerLogBase2向下舍入.最后,由于值t只是一个可能偏离1的近似值,因此通过减去v <PowersOf10 [t]的结果得到精确值.

此方法比IntegerLogBase2多运行6次.通过修改上面的log base 2 table-lookup方法,可以加速(在具有快速内存访问的机器上),以便条目保存为t计算的内容(即pre-add,-mulitply和-shift).这样做将需要总共仅9次操作来找到日志库10,假设使用了4个表(对于v的每个字节一个表).

至于计算IntegerLogBase2,该页面上有几种替代方案.它是各种高度优化的整数运算的绝佳参考.

您的版本的变体也在那里,除了它假设值(而不是值的日志基数10)是均匀分布的,因此执行指数排序的搜索:

以明显的方式查找整数的整数对数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次操作.