非常长的二进制数位相加？

Question

我被一个朋友问到：

如果2^10 = 1024，我们可以将1024分解并求和其数字: 1+0+2+4 = 7. 这很简单。

然而，当输入为2^30000(实际上是一个长字符串"1000...")时，没有任何.NET类型可以容纳这个值。

因此必须有一个技巧来求和它的数字（十进制值的数字）....

编辑：

相关技巧（用于查找10^20 - 16）

100 = 10^2（一个和两个零）

10^20 =（一个和二十个零）

因此：

10^20 - 16 = 18个9，8和4。

18 * 9 + 8 + 4 = 174

但我还没有成功地把这个解决方案转化为我的问题。（我尝试了很多次）。

*我将这个问题标记为.NET，因为我可以使用.NET库中的字符串函数、数学函数。*

问题：

有没有什么技巧可以让我求出x^n的结果中的很多数字的总和？

这里有什么技巧？

编辑#2：添加了.NET2标签（其中biginteger不可用）-我想知道如何在没有biginteger的情况下完成它。（我正在寻找隐藏的技巧）

- Royi Namir

---

“Trick”是错误的：如果你从100^20中减去33，结果将是99...9999967而不是100...0000967。 - dtb

这个相关问题有帮助吗 - http://math.stackexchange.com/q/184823 - Roger Rowland

@dtb 你说得完全正确。他们错了。我正在编辑另一个样本。（正确的） - Royi Namir

@Edwin：但这与计算2^n有何不同？ - Blender

@KenKin 不需要十进制数的每一位相加，只需要它们的总和。例如：2^12=4096。所以我想要的是4+0+9+6，即19。（而且我不需要1+9得到10再加起来得到1+0得到1）。 - Royi Namir

Answer 1

您可以利用BigInteger结构来实现。如MSDN所述，BigInteger类型是一个不可变类型，表示一个理论上没有上限或下限的任意大的整数。

基本上，在创建BigInteger实例并计算指数后，您可以将其转换为字符串。之后，您将遍历该字符串的每个字符，并将每个字符转换为int数字。将所有这些int数字相加，您就会得到答案。

BigInteger bi = new BigInteger(2);
var bi2 = BigInteger.Pow(bi, 30000);
BigInteger sum = new BigInteger();
foreach(var ch in bi2.ToString())
    sum = BigInteger.Add(sum, new BigInteger(int.Parse(ch.ToString())));
MessageBox.Show(bi2.ToString() + " - " + sum.ToString());

- Blablablaster

---

+1。很好。我不知道BigInteger可以处理任意长度。但我还是很好奇是否有什么技巧可以使用... - Royi Namir

Answer 2

我不知道有什么通用的方法可以找到一个数字的十进制位数之和。然而，有一种容易的方法可以找到一个数字的十进制位数之根。所谓“位数之和”就是所有数字的总和。例如，1024的十进制位数之和是1 + 2 + 4 = 7。65536的十进制位数之和是6 + 5 + 5 + 3 + 6 = 25。当你将位数之和重复计算直到只剩下一位数字时，你得到的便是该数字的位数之根。例如，65536的位数之和是25，所以它的位数之根是2 + 5 = 7。

这个技巧是：如果你有Z = X * Y，那么DigitRoot(Z) = DigitRoot(DigitRoot(X) * DigitRoot(Y))。（留给读者的练习：证明它！提示：从加法的同样恒等式开始证明。）

如果你有一个容易分解的数字——最容易分解的数字是2的n次方，那么就很容易递归地计算出它的位数之根：2的16次方=2的8次方* 2的8次方，所以DigitRoot(2的16次方)=DigitRoot(DigitRoot(2的8次方)*DigitRoot(2的8次方))——我们刚刚将问题简化了许多。现在我们不需要计算2的16次方，只需要计算2的8次方。当然，你也可以用这个技巧来处理2的30000次方——将它分解成DigitRoot(DigitRoot(2的15000次方)*DigitRoot(2的15000次方))。如果2的15000次方太大，那就进一步分解；一直分解到问题足够小为止。

明白了吗？

- Eric Lippert

---

十进制数字根简单地是模9。由于2和9互质，存在1<=x<=9，使得2^x = 1 (mod 9)，这里x = 6。因此，2^30000=(2^6)^5000=1 (mod 9)。 - colinfang

谢谢Eric。但是我不明白（根据你的解决方案）——如何将2^2n分解为2^n * 2^n将帮助我计算2^2n的十进制数表示的数字之和。例如：2^6=64，所以和为6+4=>10。 - Royi Namir

如果 (2^6)^5000=1 (mod 9)，那么我该如何计算数字的总和？ - Royi Namir

@RoyiNamir，Eric所说的是我们不知道任何简单的技巧来计算数字总和。上面提到的方法仅适用于数字根。 - colinfang

Answer 3

我不认为这里存在任何诡计。 你展示的后一个诡计之所以有效是因为数字和结果都是十进制数。

For example:
1267 = 1*10^3 + 2*10^2 + 6*10^1 + 7*10^0

因此，幂和总和之间存在明显的相关性。 但不幸的是，如果您想将二进制数或2的幂转换为十进制数，那么这种方法行不通。最好的办法是减小幂以增加基数。

2^3000 = 4^1500 = 16^750 = 256^375

但是，正如你所看到的，这个数列跨越了10进制的基数。这意味着在你将其转化为10的幂之前，需要将最终结果计算为一个小数。这就使得这个技巧失效了。

- Sopuli

---

2的3000次方不等于8的750次方，2的3000次方等于16的750次方。 - Blablablaster

谢谢您的纠正，我犯了一个愚蠢的错误，没有将底数乘方。 - Sopuli

这是错误的：16^750 = 256^375。应该是 16^750 = 256^749。 - Royi Namir

Answer 4

来自http://blog.singhanuvrat.com/problems/sum-of-digits-in-ab：

public class Problem_16 {
    public long sumOfDigits(int base, int exp) {
        int numberOfDigits = (int) Math.ceil(exp * Math.log10(base));
        int[] digits = new int[numberOfDigits];
        digits[0] = base;
        int currentExp = 1;

        while (currentExp < exp) {
            currentExp++;
            int carry = 0;
            for (int i = 0; i < digits.length; i++) {
                int num = base * digits[i] + carry;
                digits[i] = num % 10;
                carry = num / 10;
            }
        }

        long sum = 0;
        for (int digit : digits)
            sum += digit;

        return sum;
    }

    public static void main(String[] args) {
        int base = 2;
        int exp = 3000;
        System.out.println(new Problem_16().sumOfDigits(base, exp));
    }
}

public class Problem_16 {
    public long sumOfDigits(int base1, int exp) {
        int numberOfDigits = (int) Math.Ceiling(exp * Math.Log10(base1));
        int[] digits = new int[numberOfDigits];
        digits[0] = base1;
        int currentExp = 1;

        while (currentExp < exp) {
            currentExp++;
            int carry = 0;
            for (int i = 0; i < digits.Length; i++) {
                int num = base1 * digits[i] + carry;
                digits[i] = num % 10;
                carry = num / 10;
            }
        }

        long sum = 0;
        foreach (int digit in  digits)
            sum += digit;

        return sum;
    }
}


void Main()
{
     int base1 = 2;
        int exp = 3000000;
        Console.WriteLine (new Problem_16().sumOfDigits(base1, exp));

}

- Whit Kemmey

---

我认为他正在寻找方法，而不仅仅是代码。这种方法不依赖于BigInteger，这是他的限制条件。 - Whit Kemmey

接下来的步骤是并行化其计算——这样就可以使用所有的内核 :-) - Royi Namir