在32位系统上存储2个以上的电源31

Question

我必须编写一个程序,可以计算2 power 2010和找到数字之和的权力.例如:

if `2 power 12 => gives 4096 . So 4+0+9+6 = 19 . 

现在我需要找到相同的 2 power 2010.

请帮我理解.

Answer 1

这是让你入门的东西:

char buf[2010]; // 2^2010 < 10^2010 by a huge margin, so buffer size is safe
snprintf(buf, sizeof buf, "%.0Lf", 0x1p2010L);

Answer 2

您必须使用提供无限长整数类型的库(请参阅http://en.wikipedia.org/wiki/Bignum),或实现不需要它们的解决方案(例如,使用数字数组并实现功率计算在你自己的阵列上,在你的情况下可以像在循环中添加一样简单).由于这是家庭作业,可能是后者.

Answer 3

知道2 ^ 32,你怎么用笔和纸计算2 ^ 33？

2^32 is 4294967296

4294967296
*        2
----------
8589934592

8589934592 is 2^33; sum of digits is 8+5+8+9+...+9+2 (62)

请注意,2 ^ 2011是一个超过600位的数字:计算机没有那么多

Answer 4

GMP可能是最好的,最快的免费多架构库.它为这种计算提供了坚实的基础,不仅包括加法,还包括从字符串解析,乘法,除法,科学操作等.

关于算法本身的文献,我强烈推荐Donald Knuth的"计算机编程艺术"第2卷:研究数学算法.许多人认为本书是该主题的最佳单一参考.本书从头开始解释了如何在只能进行32位运算的机器上进行此类运算.

如果要在不使用任何工具的情况下从头开始实施此计算,则以下代码块要求仅需要提供以下其他方法:

unsigned int divModByTen(unsigned int *num, unsigned int length);
bool isZero(unsigned int *num, unsigned int length);

divModByTen应该将内存中的replace num除以num/10的值,并返回余数.除非使用库,否则实现将需要一些努力.isZero只检查内存中的数字是否全为零.有了这些,我们可以使用以下代码示例:

unsigned int div10;
int decimalDigitSum;

unsigned int hugeNumber[64];
memset(twoPow2010, 0, sizeof(twoPow2010));
twoPow2010[63] = 0x4000000;
// at this point, twoPow2010 is 2^2010 encoded in binary stored in memory

decimalDigitSum = 0;
while (!izZero(hugeNumber, 64)) {
    mod10 = divModByTen(&hugeNumber[0], 64);
    decimalDigitSum += mod10;
}

printf("Digit Sum:%d", decimalDigitSum);

Answer 5

这只需要Delphi中的几行代码...... :)

所以在c中必须相同或更短.

function PowerOf2(exp: integer): string;
var
  n     : integer;
  Digit : integer;
begin
  result := '1';
  while exp <> 0 do
  begin
    Digit := 0;
    for n := Length(result) downto 1 do
    begin
      Digit := (ord(result[n]) - ord('0')) * 2 + Digit div 10;
      result[n] := char(Digit mod 10 + ord('0'))
    end;
    if Digit > 9 then
      result := '1' + result;
    dec(exp);
  end;
end;

- - -编辑 - - -

这是1对1 c#版本.

string PowerOf2(int exp)
{
    int n, digit;
    StringBuilder result = new StringBuilder("1");
    while (exp != 0)
    {
        digit = 0;
        for (n = result.Length; n >= 1; n--)
        {
            digit = (result[n-1] - '0') * 2 + digit / 10;
            result[n-1] = Convert.ToChar(digit % 10 + '0');
        }
        if (digit > 9)
        {
            result = new StringBuilder("1" + result.ToString());
        }
        exp--;
    }
    return result.ToString();
}

int Sum(string s)
{
    int sum = 0;
    for (int i = 0; i < s.Length; i++)
    {
        sum += s[i] - '0';
    }
    return sum;
}

for (int i = 1; i < 20; i++)
{
    string s1s = PowerOf2(i);
    int sum = Sum(s1s);
     Console.WriteLine(s1s + " --> " + sum);
}