Как я могу добавить и вычесть 128-битные целые числа в C или С++, если мой компилятор их не поддерживает?

Ответ 1

Если все, что вам нужно, это сложение и вычитание, и вы уже имеете свои 128-битные значения в двоичной форме, библиотека может быть удобной, но не является абсолютно необходимой. Эта математика тривиальна для себя.

Я не знаю, что ваш компилятор использует для 64-битных типов, поэтому я буду использовать INT64 и UINT64 для 64-разрядных целых чисел с подписью и без знака.

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

Ответ 2

Взгляните на 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

Ответ 3

Наткнувшись на эту относительно старую должность полностью случайно, я подумал, что уместно подробно остановиться на предыдущей гипотезе Вольта на благо неопытных читателей.

Во-первых, подписанный диапазон 128-битного числа равен -2 ¹²⁷ до 2 ¹²⁷ -1, а не -2 ¹²⁷ до 2 ¹²⁷ как изначально было предусмотрено.

Во-вторых, из-за цикличности конечной арифметики наибольший требуемый дифференциал между двумя 128-битными числами равен -2 ¹²⁷ до 2 ¹²⁷ -1, который имеет Хранение предпосылки 128 бит, а не 129. Хотя (2 ¹²⁷ -1) - (-2 ¹²⁷) = 2 ¹²⁸ -1, что явно больше нашего максимального 2 ¹²⁷ -1 положительного целого числа, арифметическое переполнение всегда гарантирует, что ближайшее расстояние между любыми двумя числами n всегда будет находиться в диапазоне от 0 до 2 ⁿ -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 ⁿ -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 - x] + 1 должно = n - (n - x) = x.

Применив это к нашей исходной 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 при переполнении]

Является ли репрезентативная абстракция положительной, отрицательной или комбинацией обоих, как подразумевается с подписанной арифметикой twos-complement, теперь мы имеем 2 ⁿ n -битные шаблоны, которые могут без проблем обслуживать как положительные 0 до 2 ⁿ -1, так и отрицательные 0 до - (2 ⁿ) - 1 диапазон по мере необходимости. Фактически, все современные процессоры используют именно такую ​​систему для реализации общих схем ALU для операций сложения и вычитания. Когда ЦПУ встречает команду вычитания i1 - i2, она внутренне выполняет операцию [дополнение + 1] на i2 и затем обрабатывает операнды через схему сложения, чтобы вычислить i1 + [дополнение к i2] + 1. За исключением дополнительного флага переполнения/знака XOR-gated, как подписанного, так и неподписанного сложения и вычитания импликации, являются неявными.

Если применить приведенную выше таблицу к входной последовательности [-2 ^{n -1} 2 ^{n -1} -1, -2 ^{n -1}], как представлено в оригинальном ответе Volte, теперь мы можем вычислить следующие n-битовые дифференциалы:

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 ^{<я > пя > 1} 1

    (2 ^{n -1} -1) + (diff # 2) =
  3 + (-7) = (-4) =
    -2 ^{<я > пя > 1}

Возможно, вы, конечно, захотите принять более философский подход к этой проблеме и догадаться, почему для циклических последовательностей 2 ⁿ потребуется более 2 ⁿ циклически-последовательные дифференциалы?

Taliadon.

Ответ 4

Boost 1.53 теперь включает в себя многоточие:

#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

Ответ 5

Существует много литературы по большой целочисленной математике. Вы можете использовать одну из доступных библиотек (см. Ссылки), или вы можете использовать ее самостоятельно. Хотя я должен вас предупредить, для чего-то более сложного, чем сложение и вычитание (и сдвиги), вам нужно будет использовать нетривиальные алгоритмы.

Чтобы добавить и вычесть, вы можете создать класс/структуру, которая содержит два 64-битных целых числа. Вы можете использовать простую математику школы для сложения и вычитания. В основном, делайте то, что вы делаете с карандашом и бумагой для добавления или вычитания, с тщательным учетом переноса/заимствования.

Найдите большое целое число. Btw последние версии компиляторов VС++, IntelС++ и GCC имеют 128-битные целые типы, хотя я не уверен, что они так же легко доступны, как вам может понравиться (они предназначены для использования с регистрами sse2/xmms).

• http://en.wikipedia.org/wiki/Arbitrary_precision_arithmetic
• http://orion.math.iastate.edu/cbergman/crypto/bignums.html
• http://www.mathgoodies.com/tutorial/

Ответ 6

TomsFastMath немного похож на GMP (упомянутый выше), но является общедоступным, и был разработан с нуля, чтобы быть (он даже содержит оптимизацию кода сборки для x86, x86-64, ARM, SSE2, PPC32 и AVR32).

Ответ 7

Можете ли вы гарантировать, что различия будут меньше? В этом отношении, можете ли вы гарантировать, что различия на самом деле не будут больше? Например, если вы просто сохраняете числа в виде 128-битных чисел (подписанных или других), вам нужен диапазон 2 ^ 128 (либо от -2 ^ 127 до 2 ^ 127, либо от 0 до 2 ^ 128), но если вы храните различия, вам понадобится диапазон 2 ^ 129 для хранения всех потенциальных различий. Рассмотрим последовательность [-2 ^ 127, 2 ^ 127, -2 ^ 127], которая переводится в последовательность разностей [2 ^ 128, -2 ^ 128] из начальной точки -2 ^ 127. 128-битный тип данных не может содержать оба этих номера, на самом деле вам потребуется 129 бит на разницу, чтобы удерживать весь диапазон.

С другой стороны, если вы знаете, что различия между двумя числами всегда будут вписываться в меньший тип данных, я вторые соображения, чтобы посмотреть на GMP.

Ответ 8

Также стоит отметить: если целью является просто улучшить сжатие потока чисел путем предварительной обработки, то препроцессорный поток не обязательно должен быть сделан из точно арифметических различий. Вы можете использовать XOR (^) вместо + и -. Преимущество состоит в том, что 128-битный XOR точно такой же, как два независимых XOR в 64-битных частях, поэтому он является простым и эффективным.