在C语言中计算2^n的各位数字之和

Question

我新学习C语言，尝试编写一个计算2^n的所有数字和的程序，其中n<10^8。 例如，对于2^10，我们会有1+0+2+4，这是7。

以下是我编写的代码：

#include <stdio.h>
#include <math.h>

int main()
{
   int n, t, sum = 0, remainder;

   printf("Enter an integer\n");
   scanf("%d", &n);

   t = pow(2, n);

   while (t != 0)
   {
      remainder = t % 10;
      sum       = sum + remainder;
      t         = t / 10;
   }

   printf("Sum of digits of 2 to the power of %d = %d\n", n, sum);

   return 0;
}

问题在于：当数字小于30时，程序正常工作。一旦我将n设置为大于30的数字，结果始终是-47。

我真的不理解这个错误及其原因。

- flowz0r

---

你需要支持的最高 n 是多少？ - Ry-

@flowz0r：你的意思是保持int类型，同时允许任何n的值吗？所以最大可以到INT_MAX，这可能是32,767或2,147,483,647？ - Ry-

@Ry-，完全正确。它必须大于0，这是唯一的条件。没有上限。 - flowz0r

实际上，会有一个上限，所以最好弄清楚你实际需要支持什么。 - Ry-

@Ry-，就这个例子而言，我们假设n < 10^8。 - flowz0r

Answer 1

这是一个有趣的问题，但如果你想支持像你提到的 10⁸ 这样大的 n 值，我认为解决方案远超出简单答案的范畴。数字 2¹⁰⁸ 需要 10⁸+1（100,000,001）位或约 12 兆字节的内存来以二进制形式存储，在十进制下它拥有大约 3 千万位数。

你的 int 宽度为 32 位，这就是为什么有符号的 int 无法存储 2³¹，因为第 32 位是符号，而 2³¹ 在二进制中有一个后面跟着 31 个零的 1，需要 32 位而不带符号。所以它会溢出并被解释为负数。（从技术上讲，C 中有符号整数溢出是未定义行为。）

您可以切换到无符号整数以摆脱符号和未定义行为，在这种情况下，您新的最高支持的 n 将为 31。您几乎肯定可以使用 64 位整数，甚至可能是 128 位，但 2¹²⁷ 仍然远少于 2^100000000。

因此，您需要找到一种算法来计算 2 的幂的十进制位数，而不是实际存储它们（仅存储总和），或者放弃尝试使用标准 C 中的任何标量类型，并获得（或实现）在数组上操作的任意精度数学库（二进制位、十进制位或二进制编码的十进制位）。或者，您可以将解决方案限制为 uint64_t，但这时候你只能有 n < 64，可能不够有趣。=)

- Arkku

---

感谢您清晰的解释。我在一本大学计算机科学一年级练习册中发现了这个问题，所以我认为它应该很容易。我想我错了。我会尝试更深入地研究它，也许能够提出一个解决方案，因为这确实是一个有趣的问题 :) - flowz0r

Answer 2

对于 signed int t = pow(2,n)，如果 n >= 31，那么 t > INT_MAX。

您可以使用 unsigned long long t = pow(2,n) 替代。

这将允许您一直到达 n == 63。

另外，由于您使用的是基数 2，因此您可以使用 (unsigned long long)1 << n 来替代 pow(2,n)。

- goodvibration

---

1ULL << n，而不是2。 - Ry-

@Ry：是的，我想到了这个<<可能对这个人来说看起来很“奇怪”，所以我不想一次给他太多新东西。 - goodvibration

我认为这里的 63 是对 CHAR_BIT * sizeof(unsigned long long) - 1 的错字。 - Toby Speight

@TobySpeight：你说得对，上面的“31”也是如此。总的来说，这都取决于“limits.h”，但再次强调——在给定的上下文中，我认为简单的答案能更好地帮助那位（相当缺乏经验的）提问者。 - goodvibration