сложение больших целых чисел без флага переноса

Вы можете использовать «гвозди» (термин из GMP): вместо того, чтобы использовать все 64 бита uint64_t при представлении числа, используйте только 63 из них с нулевым старшим битом. Таким образом, вы можете обнаружить переполнение с помощью простого битового сдвига. Вы можете даже хотеть меньше чем 63.

Или, вы можете сделать арифметику полуслова. Если вы можете выполнять 64-битные арифметические операции, представьте свое число в виде массива uint32_t (или, что то же самое, разделите 64-битные слова на старшие и младшие 32-битные фрагменты). Затем, выполняя арифметические операции над этими 32-битными целыми числами, вы можете сначала перейти на 64-битные числа, выполнить арифметику там, а затем преобразовать обратно. Это позволяет обнаружить перенос, а также хорошо подходит для умножения, если у вас нет инструкции «умножить привет».

Как показывает другой ответ, вы можете обнаружить переполнение в неподписанном добавлении:

uint64_t sum = a + b;
uint64_t carry = sum < a;

Кроме того, хотя на практике это также будет работать в арифметике со знаком, у вас есть две проблемы:

• это более сложно
• Технически переполнение целого числа со знаком является неопределенным поведением.

поэтому вам обычно лучше придерживаться беззнаковых чисел.

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

Другими словами, если a + b меньше a, он переполняется. Конечно, это для положительных значений a и b, но это то, что вы почти наверняка будете использовать для библиотеки bignum.

К сожалению, перенос вносит дополнительную сложность в том, что добавление максимально возможного значения плюс перенос единицы даст вам то же значение, с которого вы начали. Следовательно, вы должны обрабатывать это как частный случай.

Что-то типа:

carry = 0
for i = 7 to 0:
    if a[i] > b[i]:
        small = b[i], large = a[i]
    else:
        small = a[i], large = b[i]
    if carry is 1 and large is maxvalue:
        c[i] = small
        carry = 1
    else:
        c[i] = large + small + carry
        if c[i] < large:
            carry = 1
        else
            carry = 0

На самом деле вы также можете рассмотреть возможность не использовать все биты в элементах массива.

В прошлом я реализовывал библиотеки, где максимальная «цифра» меньше или равна квадратному корню из самого высокого значения, которое она может содержать. Таким образом, для 8-битных (октетных) цифр вы сохраняете значения от 0 до 15 - таким образом, умножение двух цифр и добавление максимального переноса всегда будут соответствовать октету, что делает обнаружение переполнения спорным, хотя и за счет некоторого хранения.

Точно так же 16-битные цифры будут иметь диапазон от 0 до 255, чтобы не было переполнения на 65536.

На самом деле, я иногда ограничивал его более чем этим, гарантируя, что значение искусственного переноса равно степени десяти (таким образом, октет будет содержать от 0 до 9, 16-битные цифры будут от 0 до 99, 32-битные цифры от 0). до 9999 и так далее.

Это немного более расточительно для места, но делает преобразование в текст и обратно (например, печать ваших чисел) невероятно простым.

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

просто начните с переноса 0.

Если я вас правильно понял, вы хотите написать собственное дополнение для своего большого целочисленного типа.

Вы можете сделать это с помощью простой функции. Не нужно беспокоиться о флаге переноса при первом запуске. Просто идите справа налево, добавляйте цифру за цифрой и флаг переноса (внутри этой функции), начиная с переноса 0, и присваивайте результату (a+b+carry) %10 и переносу значение (a+ б+перенос) / 10.

этот SO может иметь значение: как реализовать большой int в c