开发者社区> 问答> 正文

计算C中2 ^ n的位数

我是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。

我真的不了解此错误以及导致此错误的原因。

展开
收起
kun坤 2019-11-29 11:42:25 457 0
1 条回答
写回答
取消 提交回答
  • 当然,这是一个有趣的问题,但是如果您希望支持较大的n值(例如您提到的10 8),那么我认为解决方案超出了简单答案的范围。数字2 10 8需要10 8 +1(100,000,001)位或大约12 MB的内存才能存储在binary中。用十进制表示,大约有3000万个数字。

    您int的位宽为32位,这就是为什么带符号的int不能存储2 31的原因 –第32位是符号,而2 31的二进制值为1,后跟31个零,因此需要32位无符号。因此它溢出并被解释为负数。(技术上签名的整数溢出是C中未定义的行为。)

    您可以切换到,unsigned int以消除符号和不确定的行为,在这种情况下,新的最高支持n将为31。几乎可以肯定,您可以使用64位整数,甚至128位整数,但是2 127仍然是小于2 亿。

    因此,您需要找到一种算法来计算2的幂的小数位数而不实际存储它们(仅存储和),或者忘记尝试在标准C中使用任何标量类型并获取(或实现)任意在数组(位,十进制数字或二进制编码的十进制数字)上运行的精密数学库。另外,您也可以将解决方案限制为,uint64_t但是,您的n <64,就不那么有趣了……=)

    2019-11-29 11:42:35
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载