17

我有一些代码可以对 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 次比较。根据肖恩的评论，我删除了 Math.Truncate。总之，这推动了大约 10% 的增长。谢谢！

4

10 回答 10

6

两个建议：

  1. 剖析并将常见案例放在首位。
  2. 在最坏的情况下进行二分搜索以最小化比较的数量。您可以使用恰好三个比较在 8 个备选方案中做出决定。

除非分布非常偏斜，否则这种组合可能不会给您带来太多收益。

于 2009-03-24T23:08:48.203 回答
6

来自 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。需要添加一个，因为 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 次操作。

于 2009-12-11T20:34:38.397 回答
2

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

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

于 2009-03-24T23:28:00.403 回答
2

我做了一些测试，这似乎比您现在拥有的代码快 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;
}
于 2009-03-24T23:56:52.750 回答
0

您在代码中评论说 10 位或更多位非常罕见，因此您的原始解决方案还不错

于 2009-03-24T23:38:18.350 回答
0

我没有对此进行测试，但基本法的变化说：

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

如果实施得当，Log2 应该比 Log10 快一点。

于 2009-03-25T07:31:35.933 回答
0 
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;
    }
于 2010-08-25T15:31:49.080 回答
-1

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

static int getLen(long x) {
    int len = 1;
    while (x > 0) {
        x = x/10;
        len++
    };
    return len
}
于 2009-03-24T23:17:58.647 回答
-1

你说的长度是什么意思？零的数量还是一切？这确实是重要的数字，但你明白了一般的想法

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");  
}
于 2009-03-24T23:26:41.577 回答
-1

这是一个简单的方法。

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.
于 2014-03-07T08:02:40.657 回答