Comment append / soustraire correctement à un nombre 128 bits (en tant que deux u_int64_t)

Je travaille en C et dois append et soustraire un nombre de 64 bits et un nombre de 128 bits. Le résultat sera conservé dans le nombre 128 bits. J’utilise un tableau entier pour stocker les moitiés supérieure et inférieure du nombre de 128 bits (c’est-à-dire u_int64_t bigNum[2] , où bigNum[0] est le moins significatif).

Quelqu’un peut-il aider avec une fonction d’addition et de soustraction pouvant prendre bigNum et y append / soustraire un u_int64_t ?

J’ai vu de nombreux exemples incorrects sur le Web, alors considérez ceci:

 bigNum[0] = 0; bigNum[1] = 1; subtract(&bigNum, 1); 

À ce stade, bigNum[0] doit avoir tous les bits définis, alors que bigNum[1] ne doit pas en avoir.

En 1re ou en 2e année, vous ne devriez pas savoir comment décomposer l’addition de 1 et 10 en parties en la divisant en plusieurs additions distinctes de dizaines et d’unités. Lorsqu’il s’agit de grands nombres, les mêmes principes peuvent être appliqués pour calculer des opérations arithmétiques sur des nombres arbitrairement grands. En réalisant que vos unités sont désormais des unités de 2 ^ bits, vos “dizaines” sont plus grandes de 2 ^ bits, etc.

Cela devrait fonctionner pour la soustraction:

 typedef u_int64_t bigNum[2]; void subtract(bigNum *a, u_int64_t b) { const u_int64_t borrow = b > a[1]; a[1] -= b; a[0] -= borrow; } 

L’addition est très similaire. Ce qui précède pourrait bien sûr être exprimé avec un test explicite aussi, mais je trouve plus propre de toujours emprunter. Optimisation laissée comme un exercice.

Pour un bigNum égal à { 0, 1 } , soustraire deux équivaut à { ~0UL, ~0UL } , ce qui correspond au modèle de bits approprié pour représenter -1. Ici, UL est supposé promouvoir un entier à 64 bits, ce qui dépend bien sûr du compilateur.

Dans le cas où la valeur que vous soustrayez est inférieure ou égale à bignum[0] vous n’avez pas à toucher bignum[1] .

Si ce n’est pas le cas, vous le soustrayez de bignum[0] , de toute façon. Cette opération s’achève, mais c’est le comportement dont vous avez besoin ici. De plus, vous devrez alors sous-traiter 1 de bignum[1] .

La plupart des compilateurs prennent en charge un type __int128 insortingnsèquement.

Essayez et vous pourriez avoir de la chance.

En assembleur, il est très facile de faire des additions / soustractions dans des entiers de longueur arbitraire quelconque, car il existe un drapeau de retenue et une instruction addition / sous-drapeau.

En C, il n’ya aucun moyen d’accéder à ce drapeau, vous devez donc le calculer vous-même. Mais cela nécessite de nombreuses manipulations. Vous pouvez utiliser une solution plus simple ici