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

Я работаю на 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] биты не должны быть установлены.


c math int128
person Joe Boo    schedule 21.01.2011    source источник
comment
К вашему сведению: существующие библиотеки, такие как GMP (gmplib.org), уже могут позаботиться об этом. Поэтому, если нет особой причины избегать этого, я бы рекомендовал использовать существующий код. А если вы хотите знать, как это сделать самостоятельно, можете заглянуть в исходный код GMP.   -  person steabert    schedule 21.01.2011
comment
Я не понимаю вашего примера. Разве 1-1 = 0, а не -1?   -  person unwind    schedule 21.01.2011
comment
GMP - это гигантский надувательский набор для поддержки всего лишь 128-битных целых чисел. Также он может случайно abort() ваша программа.   -  person R.. GitHub STOP HELPING ICE    schedule 21.01.2011
comment
Внешние библиотеки в целом слишком велики и не нужны. Я занимаюсь только простой математикой. Также, что касается вопроса 1-1 = 0 ... байты являются прямым порядком байтов (сначала наименее значимый байт). Так что это действительно будет (1 ‹< 32) -1 = 0xffffffff, надеюсь, это поможет?   -  person Joe Boo    schedule 21.01.2011
comment
Возможный дубликат Как складывать и вычитать 128-битные целые числа в C или C ++, если мой компилятор их не поддерживает?   -  person phuclv    schedule 03.05.2019

Ответы (5)


arrow_upward
1
arrow_downward

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

person Chris Becke    schedule 21.01.2011

arrow_upward
1
arrow_downward

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

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 бит, что, конечно, зависит от компилятора.

person unwind    schedule 21.01.2011
comment
Подсказка по оптимизации: некоторые (большинство?) Наборов инструкций ассемблера могут дать информацию о битах переноса при сложении и вычитании :-) - person Christoffer; 21.01.2011
comment
Я не верю, что это будет компилироваться ... возможно, вы имели в виду заимствовать = b ›› a [1] ;? Однако я не понимаю, как это может дать правильный ответ. - person Joe Boo; 21.01.2011
comment
b > a[1] - допустимое выражение в C, которое возвращает 1, если истина, и 0, если ложь. Вам нужно снова прочитать несколько книг по основам C. - person phuclv; 21.11.2014

arrow_upward
1
arrow_downward

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

add rax, r9
adc rdx, r8

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

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

Вот некоторые Пример сборки выходного

person phuclv    schedule 03.08.2013

arrow_upward
0
arrow_downward

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

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

person Jens Gustedt    schedule 21.01.2011

arrow_upward
0
arrow_downward

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

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

person Will    schedule 21.01.2011
comment
Казалось бы, реализация __int128 в gcc зависит от машины и поддерживается только тогда, когда long long имеет ширину 128 бит. Если это не так, поправьте меня. - person Joe Boo; 21.01.2011
comment
@JoeBoo long long в текущих системах всегда 64 бита. __int128 - это отдельный тип, который часто доступен только в 64-битных системах. - person phuclv; 25.01.2015