计算整数小数长度的最快方法？(.NET)
计算整数小数长度的最快方法？(.NET)
提问于 2009-03-24 23:04:45
我有一些代码对64位整数进行了大量的比较，但是它必须考虑数字的长度，就好像它被格式化为字符串一样。我不能更改调用代码，只能更改函数。
最简单的方法(除了.ToString().Length)是：
(int)Math.Truncate(Math.Log10(x)) + 1;然而，这表现得相当糟糕。因为我的应用程序只发送正值，并且长度在2和9之间相当均匀地分布(偏向于9)，所以我预先计算了这些值和have 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)运行。
更新：
我采纳了诺曼的建议，对in做了一些修改，平均只有3次比较。根据Sean的评论，我删除了Math.Truncate。总而言之，这提高了大约10%。谢谢!
回答 8
Stack Overflow用户
发布于 2009-03-24 23:28:00
这是一个二进制搜索版本，我已经测试过了，它在64位整数上工作，每次只使用五次比较。
int base10len(uint64_t n) {
int len = 0;
/* n < 10^32 */
if (n >= 10000000000000000ULL) { n /= 10000000000000000ULL; len += 16; }
/* n < 10^16 */
if (n >= 100000000) { n /= 100000000; len += 8; }
/* n < 100000000 = 10^8 */
if (n >= 10000) { n /= 10000; len += 4; }
/* n < 10000 */
if (n >= 100) { n /= 100; len += 2; }
/* n < 100 */
if (n >= 10) { return len + 2; }
else { return len + 1; }
}我怀疑这会比你已经做的更快。但这是可以预测的。
Stack Overflow用户
发布于 2009-03-24 23:56:53
我做了一些测试，这似乎比你现在的代码快2-4倍：
static int getLen(long x) {
int len = 1;
while (x > 9999) {
x /= 10000;
len += 4;
}
while (x > 99) {
x /= 100;
len += 2;
}
if (x > 9) len++;
return len;
}编辑：
下面是一个使用了更多Int32操作的版本，如果您没有x64应用程序，它应该会工作得更好：
static int getLen(long x) {
int len = 1;
while (x > 99999999) {
x /= 100000000;
len += 8;
}
int y = (int)x;
while (y > 999) {
y /= 1000;
len += 3;
}
while (y > 9) {
y /= 10;
len ++;
}
return len;
}Stack Overflow用户
发布于 2009-03-24 23:38:18
您在代码中评论说10位或更多的数字非常不常见，所以您最初的解决方案还不错
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/679602
复制相关文章
相似问题