Como posso somar e subtrair 128 bit inteiros em C ou C ++ se o meu compilador não apoiá-los?
https://stackoverflow.com/questions/741301
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou escrevendo um compressor para uma longa corrente de números de 128 bits. Eu gostaria de armazenar os números como diferenças -. Armazenando apenas a diferença entre os números em vez dos próprios números, porque eu posso arrumar as diferenças de menos bytes porque eles são menores
No entanto, para a compressão, então eu preciso subtrair esses valores de 128 bits, e para descompressão eu preciso adicionar esses valores. tamanho máximo inteiro para meu compilador é de 64 bits de largura.
Alguém tem alguma idéia para fazer isso de forma eficiente?
Solução
Se tudo que você precisa é de adição e subtração, e você já tem seus valores de 128 bits na forma binária, uma biblioteca pode ser útil, mas não é estritamente necessário. Esta matemática é simples de se fazer a si mesmo.
Eu não sei o que seus usos do compilador para tipos de 64 bits, por isso vou usar INT64 e UINT64 para quantidades inteiro de 64 bits assinados e não assinados.
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;
};
Outras dicas
Dê uma olhada 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;
}
A saída é
x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001
x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401
x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745
x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01
Depois de ter tropeçado em toda esta relativamente antigo posto inteiramente por acidente, eu pensei que pertinentes para elaborar conjecturas anterior Volte para o benefício dos leitores inexperientes.
Em primeiro lugar, o intervalo assinado de um número de 128 bits é -2 127 a 2 127 -1 e não -2 127 a 2 127 , como inicialmente previsto.
Em segundo lugar, devido à natureza cíclica da finito aritmética o maior diferencial necessária entre dois números de 128 bits é -2 127 a 2 127 -1, que tem um pré-requisito de armazenamento de 128 bits, não 129. Embora (2 127 -1) - (-2 127 ) = 2 128 -1 quais é claramente maior do que a máxima 2 127 -1 inteiro positivo, excesso aritmético sempre assegura que a distância mais próxima entre quaisquer dois n números -BIT recai sempre dentro do intervalo de 0 a 2 n -1 e, assim, implicitamente -2 n -1 a 2 n -1 -1.
Para esclarecer, vamos primeiro examinar como um processador de 3-bit hipotética implementar adição binária. Como um exemplo, considere o quadro que se segue que descreve a gama sem sinal absoluto de um número inteiro de 3 bits.
0 = 000B
1 = 001b
2 = 010B
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b ---> [Ciclos voltar para 000b no estouro]
A partir da tabela acima, é facilmente aparente que:
001B (1) + 010B (2) = 011b (3)
Também é aparente que a adição de qualquer destes números com o seu complemento numérico sempre produz 2 n -1:
010B (2) + 101b ([complemento de 2] = 5) = 111b (7) = (2 3 -1)
Devido ao transbordamento cíclico que ocorre quando a adição de dois n números resultados -BIT em um ( n 1) -bit resultado, é, por conseguinte, segue-se que a adição de qualquer destes números com o seu complemento numérico + 1 irá sempre originar 0:
010B (2) + 110b ([complemento de 2] + 1) = 000b (0)
Assim, podemos dizer que [complemento de n ] + 1 = - n , de modo que n + [complemento de n ] + 1 = n + (- n ) = 0. Além disso, se nós sabemos agora que n + [complemento de n ] + 1 = 0, em seguida, n + [complemento de n - x ] + 1 mosto = n - ( n - x ). = x
Aplicando esta a nossa mesa rendimentos 3 bits originais:
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 ---> [Ciclos para trás 000b em transbordamento]
Se a abstração figurativa é positivo, negativo ou uma combinação de ambos como implicado com assinados dois complementos aritmética, agora temos 2 n n padrões de bits que pode perfeitamente servir tanto positiva 0-2 n -1 e negativo 0 a - (2 n ) - 1 gamas como e quando necessário. Na verdade, todos os processadores modernos empregam apenas esse sistema um, a fim de implementar circuitos ALU comum para ambas as operações de adição e subtração. Quando um CPU encontra uma instrução i1 - i2 subtração, ele executa um internamente [1 complemento +] operação em i2 e subsequentemente processa os operandos através do circuito de adição, a fim de i1 computação + [complemento de i2] + 1. Com a excepção de um adicional carry / sinal bandeira estouro-gate XOR, ambos assinados e adição sem sinal, e por subtração implicação, são cada um implícito.
Se aplicarmos a tabela acima para a sequência de entrada [-2 n -1 , 2 n -1 -1, -2 n -1 ] como apresentado na resposta original de Volte, estamos agora em condições de compute os diferenciais seguinte 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
Começando com a semente -2 n -1 , que são agora capazes de reproduzir a sequência de entrada original pela aplicação de cada um dos diferenciais acima sequencialmente:
(-2 n -1 ) + (dif # 1) =
(-4) + 7 = 3 =
2 n -1 -1
(2 n -1 -1) + (dif # 2) =
3 + (-7) = (-4) =
-2 n -1
Você pode, é claro desejo de adoptar uma abordagem mais filosófica para este problema e conjecturas a respeito de porque 2 n números ciclicamente sequenciais exigiria mais do que 2 n diferenciais ciclicamente sequenciais?
Taliadon.
Aumento 1.53 agora inclui 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;
}
Output:
./a.out
c: 340282366920938463463374607431768211456
Existe muita literatura sobre grande matemática inteiro. Você pode usar uma das bibliotecas disponíveis gratuitamente (ver links) ou você pode rolar o seu próprio. Embora eu deveria avisá-lo, nada mais complicado do que adição e subtração (e turnos), você vai precisar usar algoritmos não-triviais.
Para somar e subtrair, você pode criar uma classe / estrutura que contém dois inteiros de 64 bits. Você pode usar a matemática simples escola para fazer a adição e subtração. Basicamente, fazer o que você faz com um lápis e papel para adicionar ou subtrair, tendo em devida consideração carrega / toma emprestado.
Pesquise grande inteiro. versões Btw recentes do VC ++, IntelC ++ e do CCG compiladores tem 128-bit inteiro tipos, embora eu não tenho certeza que eles são tão facilmente acessível como você pode gostar (que se destinam a ser usados ??com SSE2 / xmms registos).
TomsFastMath é um pouco como GMP (mencionados acima), mas é de domínio público, e foi projetado desde o início para ser extremamente rápido (ele ainda contém montagem otimizações de código para x86, x86-64, ARM, SSE2, PPC32 e AVR32).
Também digno de nota: se o objetivo é apenas para melhorar a compressão de um fluxo de números de pré-processamento, então o fluxo de pré-processado não tem que ser feito de diferenças exatamente aritméticas. Você pode usar XOR (^) em vez de + e -. A vantagem é que um 128 bits XOR é exactamente o mesmo que dois XORs independentes sobre as partes de 64 bits, de modo que é ao mesmo tempo simples e eficaz.
