programa - ¿Cómo puedo sumar y restar enteros de 128 bits en C o C++ si mi compilador no los admite?
suma de dos numeros enteros en c (7)
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
Estoy escribiendo un compresor para un largo flujo de números de 128 bits. Me gustaría almacenar los números como diferencias: almacenar solo la diferencia entre los números en lugar de los números en sí mismos porque puedo empaquetar las diferencias en menos bytes porque son más pequeños.
Sin embargo, para la compresión, entonces necesito restar estos valores de 128 bits, y para la descompresión necesito agregar estos valores. El tamaño máximo de enteros para mi compilador es de 64 bits de ancho.
¿Alguien tiene alguna idea para hacer esto de manera eficiente?
Echa 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
Habiendo tropezado con este post relativamente antiguo por accidente, pensé que era pertinente elaborar la conjetura previa de 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 estipuló originalmente.
En segundo lugar, debido a la naturaleza cíclica de la aritmética finita, el mayor diferencial requerido entre dos números de 128 bits es -2 127 a 2 127 -1, que tiene un requisito previo de almacenamiento de 128 bits, no 129. Aunque (2 127 -1) - (-2 127 ) = 2 128 -1 que es claramente mayor que nuestro número entero positivo máximo de 2 127 -1, el desbordamiento aritmético siempre garantiza que la distancia más cercana entre cualquiera de los dos números de n bits siempre esté dentro del rango de 0 a 2 n - 1 y por lo tanto implícitamente -2 n -1 a 2 n -1 -1.
Para aclarar, primero examinemos cómo un hipotético procesador de 3 bits implementaría la adición binaria. Como ejemplo, considere la siguiente tabla que muestra el rango absoluto sin signo de un entero de 3 bits.
0 = 000b
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b ---> [Vuelve a 000b en el desbordamiento]
De la tabla anterior es evidente que:
001b (1) + 010b (2) = 011b (3)
También es evidente que al agregar cualquiera de estos números con su complemento numérico siempre se obtienen 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 suma de dos números de n bits da como resultado un resultado de ( n + 1) bits, por lo tanto, se deduce que al agregar cualquiera de estos números con su complemento numérico + 1 siempre se obtendrá 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. Además, si ahora sabemos que n + [complemento de n ] + 1 = 0, entonces n + [complemento de n - x ] + 1 debe = n - ( n - x ) = x .
Aplicando esto a nuestros rendimientos de tabla de 3 bits originales:
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 = 100b = [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 ---> [Vuelve a 000b en el desbordamiento]
Ya sea que la abstracción de representación sea positiva, negativa o una combinación de ambas como está implícita con la aritmética de dos complementos con signo, ahora tenemos patrones de 2 n n bits que pueden servir perfectamente tanto de 0 a 2 n -1 positivos como de 0 a - (2 n ) -1 rangos como y cuando sea necesario. De hecho, todos los procesadores modernos emplean un sistema de este tipo para implementar circuitos comunes de ALU para operaciones de suma y resta. Cuando una CPU encuentra una instrucción de resta i1 - i2 , realiza internamente una operación [complemento + 1] en i2 y posteriormente procesa los operandos a través del circuito de suma para calcular i1 + [complemento de i2 ] + 1. Con la excepción de un indicador adicional de desbordamiento gordido XOR con acarreo / firma, tanto la adición con signo como la adición sin signo, y por sustracción implícita, son implícitos.
Si aplicamos la tabla anterior a la secuencia de entrada [-2 n -1 , 2 n -1 -1, -2 n -1 ] como se presenta en la respuesta original de Volte, ahora podemos calcular los siguientes diferenciales de n bits:
dif # 1:
(2 n -1 -1) - (-2 n -1 ) =
3 - (-4) = 3 + 4 =
(-1) = 7 = 111b
dif # 2:
(-2 n -1 ) - (2 n -1 -1) =
(-4) - 3 = (-4) + (5) =
(-7) = 1 = 001b
Comenzando con nuestra semilla -2 n -1 , ahora podemos reproducir la secuencia de entrada original aplicando cada uno de los diferenciales anteriores de forma secuencial:
(-2 n -1 ) + (dif # 1) =
(-4) + 7 = 3 =
2 n -1 -1
(2 n -1 -1) + (dif # 2) =
3 + (-7) = (-4) =
-2 n -1
Por supuesto, es posible que desee adoptar un enfoque más filosófico para este problema y conjeturar por qué 2 n números cíclicos secuenciales requerirían más de 2 n diferenciales cíclicamente secuenciales.
Taliadon.
Hay mucha literatura sobre matemática de enteros grandes. Puede usar una de las bibliotecas disponibles de forma gratuita (ver enlaces) o puede rodar la suya propia. Aunque debería advertirle, para algo más complicado que la suma y la resta (y los cambios), deberá usar algoritmos no triviales.
Para sumar y restar, puede crear una clase / estructura que contenga dos enteros de 64 bits. Puedes usar matemáticas simples de la escuela para hacer la suma y la resta. Básicamente, haga lo que hace con un lápiz y un papel para agregar o restar, con una consideración cuidadosa de las cargas / préstamos.
Búsqueda de entero grande. Por cierto, las versiones recientes de los compiladores VC ++, IntelC ++ y GCC tienen tipos de enteros de 128 bits, aunque no estoy seguro de que sean tan accesibles como le gustaría (están diseñados para ser utilizados con los registros sse2 / xmms).
Si todo lo que necesita es suma y resta, y ya tiene sus valores de 128 bits en forma binaria, una biblioteca puede ser útil pero no es estrictamente necesaria. Esta matemática es trivial para hacer tú mismo.
No sé qué utiliza su compilador para los tipos de 64 bits, así que usaré INT64 y UINT64 para cantidades enteras de 64 bits firmadas y sin firmar.
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;
};
También vale la pena señalar: si el objetivo es simplemente mejorar la compresión de un flujo de números mediante el preprocesamiento, entonces el flujo preprocesado no tiene que estar hecho exactamente de diferencias aritméticas. Puedes usar XOR ( ^ ) en lugar de + y - . La ventaja es que un XOR de 128 bits es exactamente igual a dos XOR independientes en las partes de 64 bits, por lo que es simple y eficiente.
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 de ensamblaje para x86, x86-64, ARM, SSE2, PPC32 y AVR32) .