stocker plus de 2 puissance 31 sur un système 32 bits

Je dois écrire un programme capable de calculer les puissances de 2 power 2010 et de trouver la sum des chiffres. par exemple:

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

Maintenant, je dois trouver la même chose pour 2 power 2010.

S’il vous plaît, aidez-moi à comprendre.

Voici quelque chose pour vous aider à démarrer:

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

Vous devez utiliser une bibliothèque fournissant des types de longueur entière illimitée (voir http://en.wikipedia.org/wiki/Bignum ) ou implémenter une solution qui n’en a pas besoin (par exemple, utiliser un tableau de chiffres et implémenter le calcul de la puissance. sur le tableau vous-même, ce qui dans votre cas peut être aussi simple qu’un ajout dans une boucle). Puisque c’est un devoir, probablement ce dernier.

Sachant que 2 ^ 32, comment calculeriez-vous 2 ^ 33 avec un stylo et du papier?

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

Sachez simplement que 2 ^ 2011 est un nombre de plus de 600 chiffres: peu de choses à faire par ordinateur

GMP est peut-être la meilleure, la plus rapide des bibliothèques multi-architecture gratuites pour cela. Il fournit une base solide pour de tels calculs, y compris non seulement l’addition, mais également l’parsing syntaxique à partir de chaînes, la multiplication, la division, les opérations scientifiques, etc.

Pour la littérature sur les algorithmes eux-mêmes, je recommande fortement The Art of Computer Programming, Volume 2: Algorithmes séminumériques de Donald Knuth . Ce livre est considéré par beaucoup comme la meilleure référence en la matière. Ce livre explique à partir de rien comment une telle arithmétique peut avoir lieu sur une machine ne pouvant effectuer que de l’arithmétique 32 bits.

Si vous souhaitez implémenter ce calcul à partir de rien sans utiliser d’outils, le bloc de code suivant requirejs uniquement que les méthodes supplémentaires suivantes soient fournies:

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

divModByTen devrait diviser remplacer num en mémoire par la valeur num / 10 et renvoyer le rest. L’implémentation demandera quelques efforts, sauf si une bibliothèque est utilisée. isZero vérifie simplement si le nombre est tout à fait en mémoire. Une fois que nous les avons, nous pouvons utiliser l’exemple de code suivant:

 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); 

Cela ne prend que quelques lignes de code dans Delphi … 🙂

Donc, c doit être identique ou plus court.

 function PowerOf2(exp: integer): ssortingng; 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; 

—–MODIFIER—–

Ceci est une version 1-à-1 c #.

 ssortingng PowerOf2(int exp) { int n, digit; SsortingngBuilder result = new SsortingngBuilder("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 SsortingngBuilder("1" + result.ToSsortingng()); } exp--; } return result.ToSsortingng(); } int Sum(ssortingng 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); } 

Voici comment calculer et imprimer 2 2010 :

 #include  #include  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 ReverseSsortingng(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; } 

Vous pouvez maintenant résumer les chiffres individuels.