计算整数小数长度的最快方法? (。净)

我有一些代码可以对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个比较来计算。

那么,我有什么其他技巧可以让这个function更快吗?

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

更新:

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

两个建议:

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

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

来自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

此方法比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次操作。

这是我测试过的二进制搜索版本,它每次只使用五次比较就可以使用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; } } 

我怀疑这会比你已经做的更快。 但这是可以预测的。

我做了一些测试,这似乎比你现在的代码快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; } 

您在代码中注释了10位数或更多位数是非常罕见的,因此您的原始解决方案也不错

我没有测试过这个,但基本法的变化说:

Log10(x)= Log2(x)/ Log2(10)

如果实现正确,Log2应该比Log10快一点。

 static int getDigitCount( int x ) { int digits = ( x < 0 ) ? 2 : 1; // '0' has one digit,negative needs space for sign while( x > 9 ) // after '9' need more { x /= 10; // divide and conquer digits++; } return digits; } 

不确定这是否更快..但你可以随时计算……

 static int getLen(long x) { int len = 1; while (x > 0) { x = x/10; len++ }; return len } 

你的长度是什么意思? 零或一切的数量? 这确实有重要的数字,但你得到了一般的想法

 public static string SpecialFormat(int v, int sf) { int k = (int)Math.Pow(10, (int)(Math.Log10(v) + 1 - sf)); int v2 = ((v + k/2) / k) * k; return v2.ToString("0,0"); } 

这是一种简单的方法。

 private static int GetDigitCount(int number) { int digit = 0; number = Math.Abs(number); while ((int)Math.Pow(10, digit++) <= number); return digit - 1; } 

如果number是unsigned int,那么“Math.Abs​​(number)”不是必需的。

我用所有数字类型制作了扩展方法。

  private static int GetDigitCount(dynamic number) { dynamic digit = 0; number = Math.Abs(number); while ((dynamic)Math.Pow(10, digit++) <= number) ; return digit - 1; } public static int GetDigit(this int number) { return GetDigitCount(number); } public static int GetDigit(this long number) { return GetDigitCount(number); } 

然后你用这个。

 int x = 100; int digit = x.GetDigit(); // 3 expected.