Come posso aggiungere e sottrarre 128 bit interi in C o C ++ se il mio compilatore non supporta loro?
https://stackoverflow.com/questions/741301
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto scrivendo un compressore per un lungo flusso di numeri a 128 bit. Vorrei memorizzare i numeri di differenze -. Memorizzando solo la differenza tra i numeri piuttosto che le stesse numeri perché mi può imballare le differenze in un minor numero di byte perché sono più piccoli
Tuttavia, per la compressione poi ho bisogno di sottrarre questi valori a 128 bit, e per la decompressione ho bisogno di aggiungere questi valori. Dimensione massima intero per il mio compilatore è ampio 64 bit.
Qualcuno ha qualche idea per fare questo in modo efficace?
Soluzione
Se tutto ciò che serve è l'addizione e la sottrazione, e avete già i vostri valori a 128 bit in forma binaria, una biblioteca potrebbe essere a portata di mano, ma non è strettamente necessario. Questa la matematica è banale per fare da soli.
Non so che cosa il vostro compilatore utilizza per i tipi a 64 bit, quindi userò INT64 e UINT64 per quantitativi interi con e senza segno a 64 bit.
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;
};
Altri suggerimenti
Date un'occhiata a 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;
}
L'uscita è
x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001
x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401
x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745
x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01
Dopo aver imbattuti in questo relativamente vecchio post del tutto per caso, ho pensato che pertinenti di approfondire precedente congettura di Volte a beneficio dei lettori inesperti.
In primo luogo, la gamma firmato di un numero di 128 bit è -2 127 2 127 -1 e non -2 127 a 2 127 , come originariamente previsto.
In secondo luogo, a causa della natura ciclica dell'aritmetica finita più grande differenziale richiesta tra due numeri a 128 bit è -2 127 2 127 -1, che ha un stoccaggio prerequisito di 128 bit, non 129. Sebbene (2 127 -1) - (-2 127 ) = 2 128 -1 che è chiaramente superiore alla nostra massima 2 127 -1 intero positivo, overflow aritmetico garantisce sempre che la distanza più vicina tra due n numeri -bit cade sempre all'interno del campo da 0 a 2 n -1 e quindi implicitamente -2 n -1 2 n -1 -1.
Per chiarire, esamineremo in primo luogo come un processore ipotetico 3 bit sarebbe implementare l'addizione binaria. Come esempio, si consideri la seguente tabella che illustra l'intervallo senza segno assoluto di un numero intero di 3 bit.
0 = 000B
1 = 001b
2 = 010B
3 = 011B
4 = 100b
5 = 101B
6 = 110b
7 = 111b ---> [Cicli torna 000b in caso di overflow]
Dalla tabella sopra è evidente che:
001b (1) + 010b (2) = 011B (3)
È evidente inoltre che l'aggiunta di uno qualsiasi di questi numeri con il suo complemento numerico produce sempre 2 n -1:
010b (2) + 101b ([complemento di 2] = 5) = 111 ter (7) = (2 3 -1)
A causa l'overflow ciclico che si verifica quando l'aggiunta di due n numeri -bit risultati in ( n 1) bit conseguenza, ne consegue che l'aggiunta uno di questi numeri con il suo complemento numerico + 1 sarà sempre resa 0:
010b (2) + 110 ter ([complemento di 2] + 1) = 000B (0)
Quindi possiamo dire che [complemento di n ] + 1 = - n , in modo che n + [complemento di n ] + 1 = n + (- n ) = 0. Inoltre, se ora sappiamo che n + [complemento di n ] + 1 = 0, allora n + [complemento di n - x ] + 1 devono = n - ( n - x ). = x
L'applicazione di questo ai nostri rendimenti da tavolo originale 3-bit:
0 = 000b = [complemento 0] + 1 = 0
1 = 001b = [complemento di 7] + 1 = -7
2 = 010B = [complemento di 6] + 1 = -6
3 = 011b = [complemento di 5] + 1 = -5
4 = 100b = [complemento di 4] + 1 = -4
5 = 101b = [complemento di 3] + 1 = -3
6 = 110b = [complemento di 2] + 1 = -2
7 = 111b = [complemento di 1] + 1 = -1 ---> [Cicli torna 000b in caso di overflow]
Se l'astrazione figurativa è positivo, negativo o una combinazione di entrambi come implicita con firmati complemento a due aritmetica, ora abbiamo 2 n n pattern -bit che può servire perfettamente sia positivo 0 a 2 n -1 e negativo 0 a - (2 n ) - 1 gamme come e quando richiesto. In realtà, tutti i processori moderni utilizzano solo un tale sistema, al fine di attuare circuiteria comune ALU sia per addizione e sottrazione operazioni. Quando una CPU incontra un'istruzione i1 - i2 sottrazione, esegue un'operazione internamente [complemento + 1] sulla i2 e successivamente elabora gli operandi attraverso la circuiteria aggiunta per calcolare i1 + [complemento di i2] + 1. Ad eccezione di un ulteriore trasportare / segno XOR-gated flag di overflow, entrambi firmati e l'aggiunta non firmato, e di conseguenza la sottrazione, sono ciascuno implicito.
Se si applica la tabella precedente per la sequenza di ingresso [-2 n -1 , 2 n -1 -1, -2 n -1 ] come presentato nella risposta originale di Volte, siamo ora in grado di compute seguenti differenziali n-bit:
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
Partendo con il nostro seme -2 n -1 , siamo ora in grado di riprodurre la sequenza di ingresso originale applicando ciascuno dei differenziali di cui sopra in sequenza:
(-2 n -1 ) + (diff # 1) =
(-4) + 7 = 3 =
2 n -1 -1
(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 n -1
Si può naturalmente desiderare di adottare un approccio più filosofico a questo problema e congetture sul motivo per cui 2 n i numeri corretti per il ciclo sequenziali richiederebbe più di 2 n differenziali corretto per il ciclo sequenziale?
Taliadon.
Boost 1.53 ora include multiprecisione:
#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;
}
Output:
./a.out
c: 340282366920938463463374607431768211456
Ci sono un sacco di letteratura per quanto riguarda la matematica grande numero intero. È possibile utilizzare una delle librerie liberamente disponibili (vedi link) oppure si può rotolare il proprio. Anche se io avverto, per qualcosa di più complicato di addizione e sottrazione (e turni), è necessario utilizzare gli algoritmi non banali.
Per aggiungere e sottrarre, è possibile creare una classe / struttura che contiene due interi a 64 bit. È possibile utilizzare la matematica semplice scuola a fare l'addizione e la sottrazione. In sostanza, fare ciò che si fa con carta e matita per aggiungere o sottrarre, con un attento esame di porta / prende in prestito.
Cerca di grandi dimensioni intero. Btw recenti versioni di VC ++, compilatori IntelC ++ e GCC hanno tipi interi a 128 bit, anche se non sono sicuro che sono facilmente accessibili come ti avrebbe fatto piacere (sono destinati ad essere utilizzati con SSE2 / xmms registri).
TomsFastMath è un po 'come GMP (di cui sopra), ma è di dominio pubblico, ed era progettato da zero per essere estremamente veloce (contiene anche ottimizzazioni del codice assembly per x86, x86-64, ARM, SSE2, PPC32 e AVR32).
Anche la pena di notare: se l'obiettivo è semplicemente quello di migliorare la compressione di un flusso di numeri pre-elaborazione, quindi il flusso di pre-elaborato non deve essere fatta di differenze esattamente aritmetici. È possibile utilizzare XOR (^) al posto di + e -. Il vantaggio è che un XOR 128 bit è esattamente lo stesso come due XOR indipendenti sulle parti a 64 bit, quindi è sia semplice ed efficiente.
