большое целое дополнение без флага переноса

Question

В языках ассемблера обычно есть инструкция, которая добавляет два операнда и перенос. Если вы хотите реализовать большие целочисленные дополнения, вы просто добавляете наименьшие целые числа без переноса и следующие целые числа с переносом. Как я могу сделать это эффективно на C или C++, где у меня нет доступа к флагом переноса? Он должен работать на нескольких компиляторах и архитектурах, поэтому я не могу просто использовать встроенную сборку или такую.

Answer 1

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

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

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

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

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

• это более сложный
• Технически, переполненные знаковое целое число не определено поведение

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

Answer 2

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

просто начать дело с переносом 0.

Answer 3

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

Иными словами, если 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 и т. д.

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

Answer 4

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

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

это SO может иметь отношение: how to implement big int in c