Как правильно сложить / вычесть 128-битное число (как два u_int64_t)
Я работаю в C и мне нужно сложить и вычесть 64-битное число и 128-битное число. Результат будет храниться в 128-битном числе. Я использую целочисленный массив для хранения верхней и нижней половин 128-битного числа (т.е. u_int64_t bigNum[2], где bigNum[0] наименее значимым).
Кто-нибудь может помочь с функцией сложения и вычитания, которая может принимать bigNum и складывать / вычитать u_int64_t к этому?
Я видел много неправильных примеров в Интернете, поэтому рассмотрим это:
bigNum[0] = 0;
bigNum[1] = 1;
subtract(&bigNum, 1);
С этой точки зрения bigNum[0] должны быть установлены все биты, в то время как bigNum[1] не должно быть никаких установленных битов.
5 ответов
В 1-м или 2-м классе вы должны научиться разбивать сложение 1 и 10 на части, разбивая его на несколько отдельных сложений по десяткам и единицам. При работе с большими числами те же принципы могут применяться для вычисления арифметических операций с произвольно большими числами, поскольку теперь ваши единицы измерения составляют 2^ биты, ваши "десятки" на 2^ бит больше и так далее.
В сборке очень легко делать сложение / вычитание в любых произвольных длинных целых числах, потому что есть флаг переноса и инструкция добавления / подчинения с флагом.
В C нет способа получить доступ к этому флагу переноса, поэтому вы должны рассчитать флаг самостоятельно. Но это требует много битовых манипуляций. Вы можете использовать более простое решение здесь
Это должно работать для вычитания:
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 бит, что, конечно, зависит от компилятора.
Для случая значение, которое вы вычитаете, меньше или равно bignum[0] тебе не нужно трогать bignum[1],
Если это не так, вы вычтите это из bignum[0]во всяком случае. Эта операция будет выполнена, но здесь вам нужно именно такое поведение. Кроме того, вам нужно будет затем 1 из bignum[1],
Большинство компиляторов изначально поддерживают тип __int128.
Попробуйте, и вам может повезти.