Как я могу добавлять и вычитать 128-битные целые числа в C или C ++, если мой компилятор их не поддерживает?
Вопрос
Я пишу компрессор для длинного потока 128-битных чисел.Я хотел бы сохранить числа как различия - сохраняя только разницу между числами, а не сами числа, потому что я могу упаковать различия в меньшее количество байт, потому что они меньше.
Однако для сжатия мне нужно вычесть эти 128-битные значения, а для распаковки мне нужно добавить эти значения.Максимальный размер целого числа для моего компилятора составляет 64 бита в ширину.
У кого-нибудь есть какие-нибудь идеи, как сделать это эффективно?
Решение
Если все, что вам нужно, это сложение и вычитание, и у вас уже есть 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;
};
Другие советы
Взгляните на 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
Совершенно случайно наткнувшись на это относительно старое сообщение, я подумал, что уместно подробнее остановиться на предыдущей гипотезе Вольте в интересах неопытных читателей.
Во-первых, диапазон знаков 128-битного числа равен -2127 до 2127-1 , а не -2127 до 2127 как и было оговорено изначально.
Во-вторых, из-за циклической природы конечной арифметики наибольшая требуемая разница между двумя 128-битными числами равна -2127 до 2127-1, который имеет обязательное условие хранения 128 бит, а не 129.Хотя (2127-1) - (-2127) = 2128-1, что явно больше нашего максимального значения 2127-1 положительное целое число, арифметическое переполнение всегда гарантирует, что ближайшее расстояние между любыми двумя n-разрядные числа всегда находятся в диапазоне от 0 до 2n-1 и , следовательно , неявно -2n-1 до 2n-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)
Также очевидно, что сложение любого из этих чисел с его числовым дополнением всегда дает 2n-1:
010b(2) + 101b ([дополнение к 2] = 5) = 111b(7) = (23-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 при переполнении]
Независимо от того, является ли репрезентативная абстракция положительной, отрицательной или комбинацией того и другого, как подразумевается в арифметике дополнения двоек со знаком, теперь у нас есть 2n n-битовые шаблоны, которые могут беспрепятственно обслуживать как положительные значения от 0 до 2n-1 и отрицательное значение от 0 до -(2n)-1 варьируется по мере необходимости.Фактически, все современные процессоры используют именно такую систему, чтобы реализовать общую схему ALU как для операций сложения, так и для операций вычитания.Когда процессор сталкивается с i1 - i2
команда вычитания, она внутренне выполняет операцию [дополнение + 1] над i2
и впоследствии обрабатывает операнды с помощью схемы сложения, чтобы вычислить i1
+ [дополнение к i2
] + 1.За исключением дополнительного флага переполнения, связанного с переносом / sign XOR-gated, как сложение со знаком, так и без знака, а также подразумеваемое вычитание являются неявными.
Если мы применим приведенную выше таблицу к входной последовательности [-2n-1, 2n-1-1, -2n-1] как представлено в первоначальном ответе Volte, теперь мы можем вычислить следующие n-разрядные дифференциалы:
разница №1:
(2n-1-1) - (-2n-1) =
3 - (-4) = 3 + 4 =
(-1) = 7 = 111b
разница №2:
(-2n-1) - (2n-1-1) =
(-4) - 3 = (-4) + (5) =
(-7) = 1 = 001b
Начиная с нашего семени -2n-1, теперь мы можем воспроизвести исходную входную последовательность , последовательно применяя каждый из вышеперечисленных дифференциалов:
(-2n-1) + (разница № 1) =
(-4) + 7 = 3 =
2n-1-1
(2n-1-1) + (разница № 2) =
3 + (-7) = (-4) =
-2n-1
Вы, конечно, можете пожелать принять более философский подход к этой проблеме и высказать предположение о том, почему 2n циклически последовательные числа потребовали бы более 2n циклически-последовательные дифференциалы?
Талиадон.
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
Существует много литературы, касающейся математики больших целых чисел.Вы можете использовать одну из библиотек, находящихся в свободном доступе (см. ссылки), или создать свою собственную.Хотя я должен предупредить вас, что для чего-либо более сложного, чем сложение и вычитание (и сдвиги), вам нужно будет использовать нетривиальные алгоритмы.
Чтобы складывать и вычитать, вы можете создать класс / структуру, которая содержит два 64-разрядных целых числа.Вы можете использовать простую школьную математику для выполнения сложения и вычитания.В основном, делайте то, что вы делаете с карандашом и бумагой, чтобы добавлять или вычитать, с тщательным учетом переноса / заимствования.
Найдите большое целое число.Кстати, последние версии компиляторов VC ++, IntelC ++ и GCC имеют 128-битные целочисленные типы, хотя я не уверен, что они так легко доступны, как вам хотелось бы (они предназначены для использования с регистрами sse2 / xmms).
TomsFastMath Томсфастмат немного похож на GMP (упомянутый выше), но является общественным достоянием и был разработан с нуля, чтобы быть чрезвычайно быстрым (он даже содержит оптимизацию ассемблерного кода для x86, x86-64, ARM, SSE2, PPC32 и AVR32).
Также стоит отметить:если цель состоит просто в том, чтобы улучшить сжатие потока чисел путем его предварительной обработки, то предварительно обработанный поток не обязательно должен состоять из точных арифметических различий.Вы можете использовать XOR (^
) вместо +
и -
.Преимущество заключается в том, что 128-битный XOR точно такой же, как два независимых XOR в 64-битных частях, поэтому он одновременно прост и эффективен.