3

给定一个大数，例如9223372036854775807( Int64.MaxValue)，求和的最快方法是什么？

目前我正在 ToStringing 并将每个字符重新解析为int：

num.ToString().Sum(c => int.Parse(new String(new char[] { c })));

这肯定是非常低效的。有什么建议么？

最后，您将如何使用BigInteger?

谢谢

4

6 回答 6

14

好吧，另一种选择是：

int sum = 0;
while (value != 0)
{
    int remainder;
    value = Math.DivRem(value, 10, out remainder);
    sum += remainder;
}

BigInteger也有一个DivRem方法，所以你可以使用相同的方法。

请注意，我发现DivRem它不如“手动”执行相同的算术那么快，所以如果您真的对速度感兴趣，您可能需要考虑这一点。

还要考虑一个带有（比如）1000 个元素的查找表，其中预先计算了总和：

int sum = 0;
while (value != 0)
{
    int remainder;
    value = Math.DivRem(value, 1000, out remainder);
    sum += lookupTable[remainder];
}

这意味着更少的迭代，但每次迭代都有一个额外的数组访问......

于 2011-03-11T17:55:27.713 回答
2

没有人讨论过 BigInteger 版本。为此，我会查看 10 1、 10 2、 10 4、 10 8等等，直到你找到最后一个小于你的值的 10 2 n 。取您的数字 div 和 mod 10 2 n来得出 2 个较小的值。清洗、漂洗并递归地重复。（您应该将 10 的迭代平方保留在一个数组中，并在递归部分传递有关下一个要使用的幂的信息。）

对于具有 k 位的 BigInteger，除以 10 是 O(k)。因此，用朴素算法求数字的总和是 O(k 2 )。

我不知道 C# 在内部使用什么，但是用于将 k 位乘以或除以 k 位整数的非朴素算法都可以在时间 O(k 1.6 ) 或更好的时间内工作（大多数要好得多，但有一个开销使它们对于“小大整数”更糟）。在这种情况下，准备您的初始权力列表并拆分一次需要时间 O(k 1.6 )。这为您提供了 2 个大小为 O((k/2) 1.6 ) = 2 -0.6 O(k 1.6 ) 的问题。在下一个级别，您有 4 个大小为 O((k/4) 1.6 ) 的问题需要另外 2 个-1.2 O(k 1.6 ) 工作。将所有项加起来，2 的幂变成一个收敛到常数的几何级数，所以总功为 O(k1.6 )。

这是一个明确的胜利，如果你使用数千位数的数字，胜利将非常非常明显。

于 2011-03-12T20:11:45.263 回答
1

是的，它可能有点效率低下。我可能只是反复除以 10，每次将余数加在一起。

于 2011-03-11T17:55:56.957 回答
1

性能优化的第一条规则：可以乘法时不要除法。以下函数将采用四位数字 0-9999 并按照您的要求进行操作。中间计算大于 16 位。我们将该数字乘以 1/10000，并将结果作为 Q16 定点数。然后通过乘以 10 并取整数部分来提取数字。

#define TEN_OVER_10000 ((1<<25)/1000 +1) // .001 Q25

int sum_digits(unsigned int n)
{
    int c;
    int sum = 0;
    n = (n * TEN_OVER_10000)>>9; // n*10/10000 Q16
    for (c=0;c<4;c++)
    {
    printf("Digit: %d\n", n>>16);
        sum += n>>16;
        n = (n & 0xffff) * 10; // next digit
    }
    return sum;
}

这可以扩展到更大的尺寸，但它很棘手。您需要确保定点计算中的舍入始终正常工作。我还做了 4 位数字，所以定点乘法的中间结果不会溢出。

于 2011-03-11T19:20:37.337 回答
1 
    Int64 BigNumber = 9223372036854775807;

    String BigNumberStr = BigNumber.ToString();
    int Sum = 0;

    foreach (Char c in BigNumberStr)
        Sum += (byte)c;

    // 48 is ascii value of zero
    // remove in one step rather than in the loop
    Sum -= 48 * BigNumberStr.Length;
于 2011-03-12T20:28:41.170 回答
0

而不是 int.parse，为什么不从每个数字中减去“0”来获得实际值。

请记住，'9' - '0' = 9，因此您应该能够按 k 顺序（数字的长度）执行此操作。减法只是一种操作，因此不应减慢速度。

于 2011-04-23T18:11:07.137 回答