Как правильно сложить / вычесть 128-битное число (как два uint64_t)?

Question

Я работаю в C и мне нужно сложить и вычесть 64-битное число и 128-битное число.Результат будет храниться в 128-битном числе.Я использую целочисленный массив для хранения верхней и нижней половин 128-битного числа (т. Е. uint64_t bigNum[2], где bigNum[0] является наименее значимым).

Может кто-нибудь помочь с функцией сложения и вычитаниячто может взять bigNum и добавить / вычесть uint64_t к нему?

Я видел много неправильных примеров в Интернете, поэтому рассмотрим следующее:

bigNum[0] = 0;  
bigNum[1] = 1;  
subtract(&bigNum, 1);

На данный момент bigNum[0] должны иметь все установленные биты, в то время как bigNum[1] не должны иметь никаких установленных битов.

Answer 1

В 1 или 2 классе вы должны научиться разбивать сложение 1 и 10 на части, разбивая его на несколько отдельных сложений по десяткам и единицам.При работе с большими числами те же принципы могут применяться для вычисления арифметических операций с произвольно большими числами, поскольку теперь ваши единицы измерения составляют 2 ^ биты, ваши "десятки" на 2 ^ бит больше и т. Д.

Answer 2

Это должно работать для вычитания:

typedef u_int64_t bigNum[2];

void subtract(bigNum *a, u_int64_t b)
{
  const u_int64_t borrow = b > a[1];

  a[1] -= b;
  a[0] -= borrow;
}

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

Для bigNum, равного { 0, 1 }, вычитание двух сделало бы его равным { ~0UL, ~0UL }, что является подходящим битовым шаблоном для представления -1.Здесь предполагается, что UL переводит целое число в 64 бита, что, конечно, зависит от компилятора.

Answer 3

Во многих архитектурах очень легко добавлять / вычитать любые произвольно длинные целые числа, потому что есть флаг переноса и добавление / суб с командой флага. Например на x86 rdx:rax += r8:r9 можно сделать вот так

add rax, r9
adc rdx, r8

В C нет доступа к этому флагу переноса, поэтому вы должны рассчитать флаг самостоятельно. Самый простой способ - проверить, меньше ли сумма без знака, чем любой из операндов , например, . Например, чтобы сделать a += b, мы сделаем так

aL += bL;
aH += bH + (aL < bL);

Вот пример примера сборки сборки

Answer 4

Большинство компиляторов поддерживают тип __ int128 .

Попробуйте, и вам может повезти.

Answer 5

В случае, если значение, которое вы вычитаете, меньше или равно bignum[0], вам не нужно прикасаться к bignum[1].

Если это не так, вы вычитаете его из bignum[0]во всяком случае.Эта операция будет выполнена, но здесь вам нужно именно такое поведение.Кроме того, вам нужно будет подключить 1 из bignum[1].