计算C中2 ^ n的位数-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

计算C中2 ^ n的位数

kun坤 2019-11-29 11:42:25 127

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

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

C语言 Windows
分享到
取消 提交回答
全部回答(1)
  • kun坤
    2019-11-29 11:42:35

    当然,这是一个有趣的问题,但是如果您希望支持较大的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,就不那么有趣了……=)

    0 0
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

推荐文章
相似问题
推荐课程