컴파일러가 지원하지 않으면 C 또는 C ++에서 128 비트 정수를 추가하고 빼려면 어떻게해야합니까?

https://stackoverflow.com/questions/741301

09-09-2019
|

문제

128 비트 숫자의 긴 스트림에 대한 압축기를 쓰고 있습니다. 숫자를 차이로 저장하고 싶습니다. 숫자 자체가 아닌 숫자의 차이 만 저장하는 것입니다.

그러나 압축의 경우이 128 비트 값을 빼야하며 감압을 위해서는이 값을 추가해야합니다. 컴파일러의 최대 정수 크기는 64 비트입니다.

누구 든지이 작업을 효율적으로 수행 할 아이디어가 있습니까?

해결책

추가 및 뺄셈이 필요한 경우 이미 이진 형태의 128 비트 값이 있으면 라이브러리가 편리하지만 엄격하게 필요하지 않습니다. 이 수학은 스스로를하기 위해 사소합니다.

컴파일러가 64 비트 유형에 무엇을 사용하는지 알지 못하므로 서명 및 서명되지 않은 64 비트 정수 수량에 int64 및 uint64를 사용하겠습니다.

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;
};

다른 팁

보세요 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;
}

출력은입니다

x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001

x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401

x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745

x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01

우연히 비교적 오래된 게시물을 넘어서서, 나는 경험이없는 독자들의 이익을 위해 Volte의 이전 추측에 대해 자세히 설명하는 것이 적절하다고 생각했습니다.

첫째, 128 비트 번호의 서명 범위는 -2입니다.¹²⁷ 2까지¹²⁷-1은 -1이 아닙니다¹²⁷ 2까지¹²⁷ 원래 규정 된대로.

둘째, 유한 산술의 주기적 특성으로 인해 두 개의 128 비트 숫자 사이의 가장 큰 차이는 -2입니다.¹²⁷ 2까지¹²⁷-1, 스토리지 전제 조건은 128 비트가 아닌 128 비트입니다.¹²⁷-1) - (-2¹²⁷) = 2¹²⁸-1은 최대 2보다 분명합니다¹²⁷-1 양의 정수, 산술 오버플로는 항상 두 사이의 가장 가까운 거리를 보장합니다. N-비트 번호는 항상 0 ~ 2 범위 내에 있습니다.^N-1이므로 암시 적으로 -2^N-1 2까지^N-1-1.

명확히하기 위해 먼저 가상의 3 비트 프로세서가 이진 첨가를 어떻게 구현하는지 살펴 보겠습니다. 예를 들어, 3 비트 정수의 절대 부호없는 범위를 나타내는 다음 표를 고려하십시오.

0 = 000b
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b ---> [오버플로에서 000b로 다시 순환

위 표에서 쉽게 분명합니다.

001B (1) + 010B (2) = 011B (3)

숫자 보완 물이있는이 숫자를 추가하면 항상 2^N-1:

010B (2) + 101B ([[보완 2] = 5) = 111b (7) = (2³-1)

두 번의 첨가 될 때 발생하는 순환 오버플로로 인해 N-비트 번호는 (N+1)-비트 결과, 따라서 숫자 보완 + 1 에이 숫자를 추가하면 항상 0을 산출합니다.

010b (2) + 110b ([2] + 1) = 000b (0)

따라서 우리는 그 말을 할 수 있습니다 N] + 1 = -N, 하도록 하다 N + [보완 N] + 1 = N + (-N) = 0. 이제 우리가 지금 알고 있다면 N + [보완 N] + 1 = 0입니다 N + [보완 N - 엑스] + 1 필수 = N - (N-엑스) = 엑스.

이것을 원래 3 비트 테이블 수율에 적용합니다.

0 = 000b = [보완 0] + 1 = 0
1 = 001b = [7] + 1 = -7
2 = 010B = [6 보완] + 1 = -6
3 = 011b = [5] + 1 = -5
4 = 100b = [4] + 1 = -4
5 = 101b = [3] + 1 = -3
6 = 110b = [2] + 1 = -2
7 = 111b = [1] + 1 = -1 ---> [오버플로에서 000b로 다시 순환]

표현 추상화가 긍정적, 부정적이든, 서명 된 두 사람의 보상 산술과 암시 된 두 가지의 조합인지 여부는 이제 2가 있습니다.^N N-긍정적 인 0 ~ 2를 원활하게 제공 할 수있는 비트 패턴^N-1 및 음수 0 ~ -(2^N) -1 범위는 필요할 때 및 필요합니다. 사실, 모든 현대 프로세서는 추가 및 뺄셈 작업을 위해 공통 ALU 회로를 구현하기 위해 이러한 시스템 만 사용합니다. CPU가 만날 때 i1 - i2 빼기 명령어는 내부적으로 [보완 + 1] 작업을 수행합니다. i2 그리고 그 후에 계산하기 위해 추가 회로를 통해 피연산자를 처리합니다. i1 + [보완 i2] + 1. 추가 캐리/사인 XOR 게이트 오버 플로우 플로우, 서명되지 않은 추가 및 서명되지 않은 추가 및 암시 적 뺄셈은 각각 암시 적입니다.

위의 표를 입력 시퀀스에 적용하면 [-2^N-1, 2^N-1-1, -2^N-1] Volte의 원래 답변에 제시된 바와 같이, 우리는 이제 다음 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

씨앗으로 시작하여 -2^N-1, 이제 우리는 위의 각 차등을 순차적으로 적용하여 원래 입력 순서를 재현 할 수 있습니다.

   (-2^N-1) + (diff #1) =
   (-4) + 7 = 3 =
   2^N-1-1

   (2^N-1-1) + (diff #2) =
   3 + (-7) = (-4) =
   -2^N-1

물론이 문제에 대한보다 철학적 접근 방식을 채택하고 왜 2^N 주기적으로 순차적으로 숫자는 2 이상이 필요합니다^N 주기적으로 순차적 차이?

탈리아 돈.

Boost 1.53은 이제 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;
}

산출:

./a.out
c: 340282366920938463463374607431768211456

큰 정수 수학에 관한 많은 문헌이 있습니다. 라이브러리 중 하나를 자유롭게 사용할 수 있거나 (링크 참조) 직접 굴릴 수 있습니다. 나는 당신에게 경고해야하지만, 추가 및 뺄셈 (및 변화)보다 더 복잡한 것에 대해서는 사소한 알고리즘을 사용해야합니다.

추가 및 빼기 위해 2 개의 64 비트 정수를 보유하는 클래스/구조를 만들 수 있습니다. 간단한 학교 수학을 사용하여 추가 및 뺄셈을 할 수 있습니다. 기본적으로 연필과 종이로 수행하는 작업을 수행하여 추가 또는 차감을 신중하게 고려하십시오.

큰 정수를 검색하십시오. BTW의 최근 버전의 VC ++, Intelc ++ 및 GCC 컴파일러에는 128 비트 정수 유형이 있지만 원하는만큼 쉽게 액세스 할 수 있는지 확실하지 않습니다 (SSE2/XMMS 레지스터와 함께 사용하려는 것).

Tomsfastmath GMP와 비슷하지만 (위에서 언급 함)는 공개 도메인이며, 접지에서 매우 빠르게 설계되었습니다 (X86, X86-64, ARM, SSE2, PPC32 및 AVR32에 대한 어셈블리 코드 최적화도 포함되어 있습니다).

또한 주목할만한 가치가 있습니다. 목표가 단지 전처리를 통해 숫자 스트림의 압축을 향상시키는 것이라면, 전처리 된 스트림은 산술적 차이를 정확하게 만들 필요가 없습니다. xor를 사용할 수 있습니다 (^) 대신에 + 그리고 -. 장점은 128 비트 XOR이 64 비트 부품의 두 개의 독립적 인 XOR과 정확히 동일하므로 간단하고 효율적이라는 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow