¿Cómo puedo sumar y restar 128 bits enteros en C o C ++ si mi compilador no admite ellos?
https://stackoverflow.com/questions/741301
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy escribiendo un compresor para una larga serie de números 128 bits. Me gustaría para almacenar los números como las diferencias -. Almacenando sólo la diferencia entre los números en lugar de los números mismos porque puedo empacar las diferencias en menos bytes porque son más pequeños
Sin embargo, para la compresión y luego tengo que restar estos valores de 128 bits, y para la descompresión tengo que añadir estos valores. El tamaño máximo de número entero para mi compilador es de 64 bits de ancho.
Alguien tiene alguna idea para hacer esto de manera eficiente?
Solución
Si todo lo que necesita es la suma y la resta, y ya tiene sus valores de 128 bits en forma binaria, una biblioteca puede ser útil, pero no es estrictamente necesario. Esta matemática es trivial para hacer usted mismo.
No sé lo que utiliza el compilador para este tipo de 64 bits, por lo que voy a utilizar Int64 y UINT64 para cantidades con y sin signo de número entero de 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;
};
Otros consejos
Tome un vistazo 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;
}
La salida es
x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001
x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401
x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745
x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01
Después de haber tropezado con este relativamente antiguo puesto totalmente por accidente, pensé que es pertinente para elaborar en una conjetura anterior Volte para el beneficio de los lectores inexpertos.
En primer lugar, el rango firmado de un número de 128 bits es -2 127 a 2 127 -1 y no -2 127 a 2 127 como se estipula originalmente.
En segundo lugar, debido a la naturaleza cíclica de la aritmética finita el mayor diferencial requerida entre dos números 128 bits es -2 127 a 2 127 -1, que tiene una requisito de almacenamiento de 128 bits, no 129. Aunque (2 127 -1) - (-2 127 ) = 2 128 -1 cual es claramente mayor que nuestro máximo 2 127 -1 entero positivo, desbordamiento aritmético siempre se asegura de que la distancia más cercana entre dos n números -bit siempre cae dentro del rango de 0 a 2 n -1 y por lo tanto implícitamente -2 n -1 a 2 n -1 -1.
Con el fin de aclarar, primero vamos a examinar cómo un procesador hipotético de 3 bits implementaría suma binaria. Como un ejemplo, considere la siguiente tabla que representa el rango sin signo absoluto de un número entero de 3 bits.
0 = 000b
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b ---> [Ciclos de nuevo a 000b en desbordamiento]
A partir de la tabla anterior es fácilmente evidente que:
001b (1) + 010b (2) = 011b (3)
También es evidente que la adición de cualquiera de estos números con su complemento numérico siempre produce 2 n -1:
010b (2) + 101b ([complemento de 2] = 5) = 111b (7) = (2 3 -1)
Debido al desbordamiento cíclico que se produce cuando la adición de dos n números -bit resultados en un ( n 1) bits resultado, por lo tanto, se deduce que la adición de cualquiera de estos números con su complemento numérico + 1 siempre producirá 0:
010b (2) + 110b ([complemento de 2] + 1) = 000b (0)
Así, podemos decir que [complemento de n ] + 1 = - n , de modo que n + [complemento de n ] + 1 = n + (- n ) = 0. Por otra parte, si ahora sabemos que n + [complemento de n ] + 1 = 0, entonces n + [complemento de n - x ] + 1 debe ser = n - ( n - x ). = x
Aplicando esto a nuestros rendimientos originales de la tabla 3 bits:
0 = 000b = [complemento de 0] + 1 = 0
1 = 001b = [complemento de 7] + 1 = -7
2 = 010b = [complemento de 6] + 1 = -6
3 = 011b = [complemento de 5] + 1 = -5
4 = 100 B = [complemento de 4] + 1 = -4
5 = 101b = [complemento de 3] + 1 = -3
6 = 110b = [complemento de 2] + 1 = -2
7 = 111b = [complemento de 1] + 1 = -1 ---> [Ciclos de nuevo a 000b en desbordamiento]
Si la abstracción figurativa es positivo, negativo o una combinación de ambos como se implica con la aritmética firmados complemento a dos, ahora tenemos 2 n n patrones -bit que pueden servir sin problemas tanto positivas 0 a 2 n -1 y negativo 0 a - (2 n ) - 1 rangos como y cuando sea necesario. De hecho, todos los procesadores modernos emplean sólo un sistema de este tipo con el fin de implementar circuitos comunes ALU tanto para las operaciones de sustracción y adición. Cuando una CPU se encuentra con una instrucción i1 - i2 resta, internamente realiza una operación de [complementar + 1] en i2 y posteriormente procesa los operandos a través de los circuitos de adición con el fin de calcular i1 + [complemento de i2] + 1. Con la excepción de un adicional de Llevamos / signo indicador de desbordamiento XOR-cerrada, ambos firmados y además sin firmar, y por sustracción implicación, son cada uno implícita.
Si aplicamos la tabla anterior para la secuencia de entrada [-2 n -1 , 2 n -1 -1, -2 n -1 ] como se presenta en respuesta original de Volte, que ahora son capaces de compute las siguientes diferencias de n bits:
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
A partir de nuestra semilla -2 n -1 , que ahora son capaces de reproducir la secuencia de entrada original mediante la aplicación de cada uno de los diferenciales anteriores secuencialmente:
(-2 n -1 ) + (diff # 1) =
(-4) + 7 = 3 =
2 n -1 -1
(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 n -1
Por supuesto, puede adoptar un enfoque más filosófico a este problema y conjeturas en cuanto a porqué 2 n números en función del ciclo secuenciales requeriría más de 2 n diferenciales en función del ciclo secuenciales?
Taliadon.
Boost 1.53 ahora incluye multiprecision:
#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;
}
Salida:
./a.out
c: 340282366920938463463374607431768211456
Hay una gran cantidad de literatura sobre grandes operaciones aritméticas con enteros. Puede utilizar una de las bibliotecas de libre disposición (ver enlaces) o puede liar. Aunque hay que advertir que, para cualquier cosa más complicada que la suma y la resta (y turnos), tendrá que utilizar algoritmos no triviales.
Para sumar y restar, puede crear una clase / estructura que sostiene dos enteros de 64 bits. Puede utilizar matemáticas de la escuela sencillo de hacer la suma y la resta. Básicamente, hacer lo que haces con un lápiz y papel para sumar o restar, con una cuidadosa consideración a lleva / toma prestado.
Búsqueda de número entero grande. versiones cierto recientes de VC ++, compiladores IntelC ++ y del CCG tienen tipos enteros de 128 bits, aunque no estoy seguro de que son tan fácilmente accesibles como le gustaría (que están destinados a ser utilizados con SSE2 / xmms registros).
TomsFastMath es un poco como GMP (mencionado anteriormente), pero es de dominio público, y fue diseñado desde cero para ser extremadamente rápido (incluso contiene optimizaciones de código ensamblador para x86, x86-64, ARM, SSE2, PPC32 y AVR32).
También digno de mención: si el objetivo es simplemente para mejorar la compresión de una serie de números de pre-procesamiento, entonces la corriente de pre-procesado no tiene que ser hecho de las diferencias aritméticas con exactitud. Puede utilizar XOR (^) en lugar de + y -. La ventaja es que un XOR 128 bits es exactamente el mismo que dos XORs independientes sobre las partes de 64 bits, por lo que es a la vez simple y eficiente.
