在32位系統上存儲超過2個電源31

Question

我必須編寫一個程序，該程序可以計算2 power 2010的功率並查找數字的總和。例如：

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

現在我需要找到同爲2 power 2010.

請幫我明白了。

Answer 1

您必須使用提供無限整數長度類型的庫（請參閱http://en.wikipedia.org/wiki/Bignum），或實施不需要它們的解決方案（例如，使用數字陣列並自行對陣列實施功率計算，這在您的情況可以像循環中的添加一樣簡單）。由於這是作業，可能是後者。

Answer 2

認識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 3

這裏的東西，讓你開始：

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

Answer 4

GMP也許是最好的，最快的免費多架構庫。它爲這種計算提供了堅實的基礎，不僅包括加法，還包括從字符串解析，乘法，除法，科學操作等。

對於算法本身的文獻，我強烈推薦The Art of Computer Programming, Volume 2: Seminumerical Algorithms by Donald Knuth。本書被許多人認爲是該主題的最佳單一參考。本書從頭開始介紹如何在只能進行32位算術運算的機器上進行這樣的算法。

如果你想從頭開始實現這個計算，而無需使用任何工具，下面的代碼塊需要只需要下面的其他方法來提供：

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

divModByTen要分取代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

這裏是你如何計算和打印2 ：

#include <stdio.h> 
#include <string.h> 

void AddNumbers(char* dst, const char* src) 
{ 
    char ddigit; 
    char carry = 0; 

    while ((ddigit = *dst) != '\0') 
    { 
    char sdigit = '0'; 

    if (*src != '\0') 
    { 
     sdigit = *src++; 
    } 

    ddigit += sdigit - '0' + carry; 

    if (ddigit > '9') 
    { 
     ddigit -= 10; 
     carry = 1; 
    } 
    else 
    { 
     carry = 0; 
    } 

    *dst++ = ddigit; 
    } 
} 

void ReverseString(char* s) 
{ 
    size_t i, n = strlen(s); 

    for (i = 0; i < n/2; i++) 
    { 
    char t = s[i]; 
    s[i] = s[n - 1 - i]; 
    s[n - 1 - i] = t; 
    } 
} 

int main(void) 
{ 
    char result[607], tmp[sizeof(result)]; 
    int i; 

    memset (result, '0', sizeof(result)); 
    result[0] = '1'; 
    result[sizeof(result) - 1] = '\0'; 

    for (i = 0; i < 2010; i++) 
    { 
    memcpy(tmp, result, sizeof(result)); 
    AddNumbers(result, tmp); 
    } 

    ReverseString(result); 
    printf("%s\n", result); 

    return 0; 
} 

您現在可以總結個別數字。

Answer 6

這需要在Delphi的代碼只有幾行... :)

所以在Ç必須相同或者更短。

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; 

----- ----- EDIT

這是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); 
}