When doing a math operation, how can I get the part that overflowed?

For example, assuming 32-bit ints:

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

In this case, `c`

is `0xfffffffe`

, but the answer should be `0x1fffffffe`

. How do I get the 1 that overflowed?

How can I do the same for multiplication? Can I multiply two large numbers together and only get the overflowed part?

How do bigint libraries manage this?

@Warning NOT PORTABLE@

Example: 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);
}
```

- Use inline assembly to read the carry flag

answered on Stack Overflow Feb 23, 2020 by P__J__

Assuming unsigned type operands, you can write:

```
bool cf = a+b<a;
```

or

```
bool cf = a>-1-b;
```

These work regardless of the existence of a larger type to work with.

Multiplication is harder; without a larger type, there is no way to access the upper half of the result. If you do have one you can use it. For example, if your operands are `uint32_t`

,

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

Otherwise, you're stuck dropping to a half-sized type and using long multiplication. For example, with `uint64_t a,b;`

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

And then the upper part of the result is `ah*bh`

plus the carry out of adding `al*bh`

, `ah*bl`

, and the upper bits of `al*bl`

.

Bigint libraries can avoid the pain of this by just choosing a limb type that's at most half the width of the largest integer type.

answered on Stack Overflow Feb 23, 2020 by R.. GitHub STOP HELPING ICE

How do I get the 1 that overflowed?

To do it afterwards in a portable way (not forgetting that `unsigned int`

might only be 16 bits):

```
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;
}
```

To do it beforehand in a portable way (without branches):

```
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;
```

How can I do the same for multiplication?

Multiplication doesn't have a carry, it has an "upper half". Specifically; if you multiply an unsigned integer that has N bits with an unsigned integer that has M bits then the result will have N+M bits; and if both numbers had the same size then the result will be twice as big.

Sadly C doesn't support "result type is larger than source/s types", so you need to "pre-promote" the source types, like:

```
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;
```

Of course if the compiler doesn't support a larger type then you have to split it into smaller pieces, like:

```
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;
```

How do bigint libraries manage this?

Mainly; they use inline assembly language because most CPUs support instructions to work on bigger integers efficiently and/or because you can access the carry flag directly. For example; for 80x86; the CPU has `adc`

/`sbb`

, `shld`

/`shrd`

, `mul`

(with double width result)/`div`

(with double width numerator); plus maybe extensions (`adcx`

and `adox`

).

In 32-bit 80x86 assembly language, the addition might look like:

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

..and the multiplication might look like:

```
mul ebx ;edx:eax = a * b
```

answered on Stack Overflow Feb 23, 2020 by Brendan

User contributions licensed under CC BY-SA 3.0