Получить переполнение от арифметических c операций

Question

При выполнении математической операции, как я могу получить часть, которая переполнилась?

Например, предполагая 32-битные числа:

unsigned int a = 0Xffffffff;
unsigned int b = 0xffffffff;
unsigned int c = a + b;

В этом случае c 0xfffffffe, но ответ должен быть 0x1fffffffe. Как получить переполненную 1?

Как сделать то же самое для умножения? Могу ли я умножить два больших числа вместе и получить только переполненную часть?

Как библиотеки bigint управляют этим?

Answer 1

Принимая операнды беззнакового типа, вы можете написать:

bool cf = a+b<a;

или

bool cf = a>-1-b;

Они работают независимо от наличия большего типа для работы.

Умножение сложнее; без более крупного типа невозможно получить доступ к верхней половине результата. Если у вас есть, вы можете использовать его. Например, если ваши операнды uint32_t,

uint32_t upper = ((uint64_t)a * b) >> 32;
uint32_t lower = a*b;

В противном случае вы застряли, опускаясь до типа половинного размера и используя длинное умножение. Например, с uint64_t a,b;

uint32_t al = a, ah = a>>32;
uint32_t bl = b, bh = b>>32;

И тогда верхняя часть результата равна ah*bh плюс выполнение сложения al*bh, ah*bl и верхних битов al*bl .

Библиотеки Bigint могут избежать этого, просто выбрав тип конечности, длина которого не превышает половины ширины целочисленного типа.

Answer 2

Как получить переполненную 1?

Чтобы сделать это впоследствии переносимым способом (не забывая, что unsigned int может быть только 16 битами):

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;
    uint32_t c_low = a + b;
    uint32_t c_high;
    if(c_low >= a) {
        c_high = 0;
    } else {
        c_high = 1;
    }

Чтобы сделать это заранее переносимым способом (без ответвлений):

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;
    uint32_t c_low;
    uint32_t c_high;

    c_high = (a&b) >> 31;
    c_low = (a ^ (c_high<<31)) + b;

Как сделать то же самое для умножения?

Умножение не нести, у него есть "верхняя половина". В частности, если вы умножите целое число без знака, которое имеет N битов, на целое число без знака, которое имеет M битов, то результат будет иметь N + M битов; и если оба числа имели одинаковый размер, то результат будет в два раза больше.

К сожалению, C не поддерживает «тип результата больше, чем тип источника / s», поэтому вам необходимо «предварительно продвигать "исходные типы, такие как:

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;
    uint64_t temp = (uint64_t)a * (uint64_t)b;
    uint32_t c_low = temp;
    uint32_t c_high = temp >> 32;

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

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;

    uint32_t a_low = a & 0xFFFF;
    uint32_t a_high = a >> 16;
    uint32_t b_low = a & 0xFFFF;
    uint32_t b_high = b >> 16;

    uint32_t temp_0 = a_low * b_low;
    uint32_t temp_16a = a_high * b_low;
    uint32_t temp_16b = a_low * b_high;
    uint32_t temp_32 = a_high * b_high;

    uint32_t c_low = temp_0 + (temp16a << 16) + (temp16b << 16);
    uint32_t c_high = (temp16a >> 16) + (temp16b >> 16) + temp_32;

Как библиотеки bigint управляют этим?

Преимущественно; они используют встроенный язык ассемблера, потому что большинство процессоров поддерживают инструкции для эффективной работы с большими целыми числами и / или потому что вы можете получить прямой доступ к флагу переноса. Например; для 80х86; ЦП имеет adc / sbb, shld / shrd, mul (с результатом двойной ширины) / div (с числителем двойной ширины); плюс может быть расширения (adcx и adox).

На 32-битном языке ассемблера 80x86 добавление может выглядеть следующим образом:

    xor edx,0
    add eax,ebx      ;c_low = a + b
    adc edx,0        ;c_high = carry

.. и умножение может выглядеть следующим образом :

    mul ebx          ;edx:eax = a * b

Answer 3

@ Предупреждение НЕ ПОРТАТИВНО @

1. Использование https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

Пример: https://godbolt.org/z/NcyNzR

#include <stdio.h> 
int main(void)
{
    unsigned int res;

    if(__builtin_uadd_overflow(0Xffffffff, 0Xffffffff, &res))
    {
        printf("Overflowed\n");
    }
    printf("Result: 0x%x\n", res);
}

Используйте встроенную сборку, чтобы прочитать флаг переноса