Comment puis-je ajouter et soustraire 128 entiers de bits en C ou C ++ si mon compilateur ne les supporte pas?
https://stackoverflow.com/questions/741301
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'écris un compresseur pour un long jet de nombres de 128 bits. Je voudrais enregistrer les numéros que les différences -. Mémorisation la différence entre les chiffres plutôt que les chiffres eux-mêmes parce que je peux emballer les différences dans moins d'octets, car ils sont plus petits
Cependant, pour la compression alors je besoin de soustraire ces 128 valeurs de bits, et pour la décompression, je besoin d'ajouter ces valeurs. la taille de l'entier maximum pour mon compilateur est de 64 bits de large.
Quelqu'un a des idées pour le faire efficacement?
La solution
Si vous avez besoin est l'addition et la soustraction, et vous avez déjà vos valeurs 128 bits sous forme binaire, une bibliothèque peut-être à portée de main mais n'est pas strictement nécessaire. Ce calcul est trivial pour vous faire.
Je ne sais pas ce que votre compilateur utilise pour les types 64 bits, donc je vais utiliser INT64 et Uint64 pour signées et des quantités non signés entiers 64 bits.
class Int128
{
public:
...
Int128 operator+(const Int128 & rhs)
{
Int128 sum;
sum.high = high + rhs.high;
sum.low = low + rhs.low;
// check for overflow of low 64 bits, add carry to high
if (sum.low < low)
++sum.high;
return sum;
}
Int128 operator-(const Int128 & rhs)
{
Int128 difference;
difference.high = high - rhs.high;
difference.low = low - rhs.low;
// check for underflow of low 64 bits, subtract carry to high
if (difference.low > low)
--difference.high;
return difference;
}
private:
INT64 high;
UINT64 low;
};
Autres conseils
Jetez un oeil à GMP .
#include <stdio.h>
#include <gmp.h>
int main (int argc, char** argv) {
mpz_t x, y, z;
char *xs, *ys, *zs;
int i;
int base[4] = {2, 8, 10, 16};
/* setting the value of x in base 10 */
mpz_init_set_str(x, "100000000000000000000000000000000", 10);
/* setting the value of y in base 16 */
mpz_init_set_str(y, "FF", 16);
/* just initalizing the result variable */
mpz_init(z);
mpz_sub(z, x, y);
for (i = 0; i < 4; i++) {
xs = mpz_get_str(NULL, base[i], x);
ys = mpz_get_str(NULL, base[i], y);
zs = mpz_get_str(NULL, base[i], z);
/* print all three in base 10 */
printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs);
free(xs);
free(ys);
free(zs);
}
return 0;
}
La sortie est
x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001
x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401
x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745
x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01
Après avoir trébuché à travers ce tout poste relativement vieux par accident, je pensais qu'il est pertinent d'élaborer sur des conjectures précédente Volte au profit des lecteurs inexpérimentés.
Tout d'abord, la plage d'un nombre signé de 128 bits est de -2 127 2 127 -1 et -2 ne 127 de 2 127 comme initialement prévu.
D'autre part, en raison de la nature cyclique de l'arithmétique finie le plus grand écart nécessaire entre les deux nombres de 128 bits est -2 127 2 127 -1, qui a une le stockage préalable de 128 bits, pas 129. Bien (2 127 -1) - (-2 127 ) = 2 128 -1 qui est nettement plus grand que notre maximale 2 127 -1 entier positif, dépassement arithmétique assure toujours que la distance la plus proche entre deux quelconques n numéros de -bit tombe toujours dans la fourchette de 0 à 2 n -1 et donc implicitement -2 n -1 2 n -1 -1.
Afin de clarifier, examinons d'abord comment un hypothétique processeur 3 bits serait mise en œuvre plus binaire. A titre d'exemple, considérons le tableau ci-dessous qui représente l'intervalle non signé absolue d'un nombre entier de 3 bits.
0 = 000B
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b ---> [Cycles retour à 000b en cas de débordement]
Dans le tableau ci-dessus, il est évident que:
001b (1) + 010b (2) = 011b (3)
Il est également évident que l'ajout d'un de ces numéros avec son complément numérique donne toujours 2 n -1:
010b (2) + 101b ([complément 2] = 5) = 111b (7) = (2 3 -1)
En raison du débordement cyclique qui se produit lorsque l'addition de deux n numéros de -bit résultats dans un ( n 1) bits conséquence, il en résulte donc que l'ajout un de ces numéros avec son complément numérique + 1 donnera toujours 0:
010b (2) + 110b ([complément 2] + 1) = 000b (0)
On peut donc dire que [complément de n ] + 1 = - n , de sorte que n + [complément de n ] + 1 = n + (- n ) = 0. De plus, si nous savons maintenant que n + [complément de n ] + 1 = 0, n + [complément de n - x ] + 1 doit = n - ( n - x ). = x
Appliqué à nos rendements de table 3 bits d'origine:
0 = 000b = [complément de 0] + 1 = 0
1 = 001b = [complément 7] + 1 = -7
2 = 010b = [complément 6] + 1 = -6
3 = 011b = [complément 5] + 1 = -5
4 = 100b = [complément 4] + 1 = -4
5 = 101b = [complément 3] + 1 = -3
6 = 110b = [complément 2] + 1 = -2
7 = 111b = [complément 1] + 1 = -1 ---> [Cycles retour à 000b en cas de dépassement]
Que l'abstraction représentationnel est positif, négatif ou une combinaison des deux comme implicite avec l'arithmétique complément à deux signés, nous avons maintenant 2 n n modèles de -bit qui peut parfaitement servir à la fois positifs 0 à 2 n -1 et 0 négatif à - (2 n ) - 1 intervalles en cas de besoin. En fait, tous les processeurs modernes utilisent un tel système afin de mettre en œuvre des circuits communs ALU pour les opérations d'addition et de soustraction. Lorsqu'une CPU rencontre une instruction de soustraction de i1 - i2, il réalise à l'intérieur d'une opération [compléter + 1] sur i2 et traite ensuite les opérandes à travers le circuit d'addition pour calculer i1 + [complément de i2] + 1. A l'exception d'un supplément porter / signe indicateur de débordement XOR-fermée, tous deux signés et non signés outre, et par soustraction d'implication, sont chacun implicite.
Si l'on applique le tableau ci-dessus pour la séquence d'entrée [-2 n -1 , 2 n -1 -1, -2 n -1 ] tel que présenté dans la réponse initiale Volte, nous sommes maintenant en mesure de compute les différentiels n bits suivants:
diff # 1:
(2 n -1 -1) - (-2 n -1 ) =
3 - (-4) = 3 + 4 =
(-1) = 7 = 111b
diff # 2:
(-2 n -1 ) - (2 n -1 -1) =
(-4) - 3 = (-4) + (5) =
(-7) = 1 = 001b
À partir de nos semences -2 n -1 , nous sommes maintenant en mesure de reproduire la séquence d'entrée d'origine en appliquant chacune des différences ci-dessus séquentiellement:
(-2 n -1 ) + (diff # 1) =
(-4) + 7 = 3 =
2 n -1 -1
(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 n -1
Vous pouvez bien vouloir bien sûr d'adopter une approche plus philosophique à ce problème et de conjectures pour expliquer pourquoi 2 n numéros de manière cyclique séquentielles nécessiterait plus de 2 n différentiels cycliquement séquentielles?
Taliadon.
Boost 1,53 comprend maintenant Multiprécision:
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
// Requires Boost 1.53 or higher
// build: g++ text.cpp
int main()
{
namespace mp = boost::multiprecision;
mp::uint128_t a = 4294967296;
mp::uint256_t b(0);
mp::uint512_t c(0);
b = a * a;
c = b * b;
std::cout << "c: " << c << "\n";
return 0;
}
Sortie:
./a.out
c: 340282366920938463463374607431768211456
Il y a beaucoup de littérature en ce qui concerne les mathématiques grand entier. Vous pouvez utiliser l'une des bibliothèques disponibles gratuitement (voir les liens) ou vous pouvez rouler votre propre. Bien que je dois vous avertir, pour quoi que ce soit plus compliqué que addition et la soustraction (et déplacements), vous aurez besoin d'utiliser des algorithmes non triviaux.
Pour ajouter et soustraire, vous pouvez créer une classe / structure qui contient deux entiers 64 bits. Vous pouvez utiliser des maths simples de l'école pour faire l'addition et la soustraction. En fait, faire ce que vous faites avec un crayon et du papier pour ajouter ou soustraire, avec une attention particulière à porte / emprunte.
Rechercher grand entier. BTW versions récentes de VC ++, IntelC ++ et compilateurs GCC ont des types entiers de 128 bits, bien que je ne suis pas sûr qu'ils sont aussi facilement accessibles que vous pourriez vous (ils sont destinés à être utilisés avec des registres SSE2 / XMMS).
TomsFastMath est un peu comme les BPF (mentionné ci-dessus), mais est du domaine public, et a été conçu à partir du sol pour être extrêmement rapide (il contient même des optimisations de code assembleur pour x86, x86-64, ARM, SSE2, PPC32 et AVR32).
A noter également: si l'objectif est simplement d'améliorer la compression d'un flux de nombres par prétraiter, puis le flux prétraité ne doit pas être fait des différences exactement arithmétiques. Vous pouvez utiliser XOR (^) au lieu de + et -. L'avantage est qu'un 128 bits XOR est exactement le même que deux XORs indépendants sur les parties 64 bits, il est à la fois simple et efficace.
