计算整数的小数长度的最快方法？ （。网）

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. 进行二分搜索以最大限度地减少最坏情况下的比较次数。 您可以通过 3 次比较在 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]);

以 10 为底的整数对数计算公式为
首先使用其中一种技术
上面求对数底数 2。
关系 log10(v) = log2(v) /
log2(10)，我们需要将其乘以
1/log2(10)，大约为
1233/4096，或 1233 后跟一个右
移位 12。需要加 1
因为 IntegerLogBase2 舍入
向下。 最后，由于 t 的值是
只是一个可能有偏差的近似值
加一，精确值可以通过以下方式找到
减去 v < 的结果
PowersOf10[t]。

此方法还需要 6 次操作
比 IntegerLogBase2。 可能会被加速
up（在具有快速内存的机器上
访问）通过修改日志底数2
上面的查表方法使得
条目保存 t 的计算结果
（即预加、-乘和
-转移）。 这样做总共只需要 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 次操作
平均。

Answer 3

这是我已经测试过的二进制搜索版本，它适用于 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; }
}

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

Answer 4

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

Answer 5

你在代码中评论说10位或更多是非常罕见的，所以你原来的解决方案还不错

Answer 6

我还没有对此进行测试，但基本定律的变化表明：

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

如果实施正确，Log2 应该比 Log10 快一点。

Answer 7

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;
    }

Answer 8

不确定这是否更快..但你总是可以数...

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

Answer 9

你说的长度是什么意思？ 零的数量还是全部？ 这 的数字很重要，但您可以了解总体思路

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");  
}

Answer 10

这是一个简单的方法。

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.