12

I want to get the carry bit of adding two unsigned 64-bit integers in c. I can use x86-64 asm if needed. code:

#include <stdio.h>

typedef unsigned long long llu;

int main(void){
  llu a = -1, b = -1;
  int carry = /*carry of a+b*/;
  llu res = a+b;
  printf("a+b = %llu (because addition overflowed), carry bit = %d\n", res, carry);
  return 0;
}
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
neo5003
  • 131
  • 1
  • 7
  • 4
    Can you use GCC or Clang built-ins? `carry = __builtin_add_overflow(a, b, &res)` stores the low bits of the result in `res` and sets `carry` to if overflow occurred. (The function actually returns a `bool` that is `true` or `false`, so assigning it to `carry` will produce 1 or 0.) – Eric Postpischil May 07 '19 at 17:14
  • 1
    Note that msvc (if that's what you are using) also has a builtin for efficiently handling overflow ([_addcarry_u64](https://learn.microsoft.com/en-us/cpp/intrinsics/x64-amd64-intrinsics-list?view=vs-2019)). – David Wohlferd May 07 '19 at 19:54
  • Why do you assing `-1` to an unsigned int number? That is Undefined Behaviour and you can get anything from that, even a program crash. – Luis Colorado May 09 '19 at 11:10

2 Answers2

9

As @EugeneSh. observes, the carry is either 0 or 1. Moreover, given that a and b both have the same unsigned type, their sum is well defined even if the arithmetic result exceeds the range of their type. Moreover, the (C) result of the sum will be less than both a and b when overflow occurs, and greater otherwise, so we can use the fact that C relational operations evaluate to either 0 or 1 to express the carry bit as

carry = (a + b) < a;

That does not require any headers, nor does it depend on a specific upper bound, or even on a and b having the same type. As long as both have unsigned types, it reports correctly on whether the sum overflows the wider of their types or unsigned int (whichever is wider), which is the same as their sum setting the carry bit. As a bonus, it is expressed in terms of the sum itself, which I think makes it clear what's being tested.

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
  • 3
    Warning: extending this to `carry_out = (a + b + carry_in) < a` *doesn't* work, because for example `b = 0xFFFF...` and `carry_in = 1` has already produced a carry that you won't detect with `a + 0 < a` being false. But yes, for add with carry-out but not carry-in, this works great. And modern compilers often can optimize `c+d + carry` into an `adc` instruction. You only run into big problems getting compilers to emit a chain of add/adc/adc/adc where you need to use the carry-out from an `adc`, not `add`. – Peter Cordes May 07 '19 at 20:41
  • "As long as both have unsigned types ..." + " and at least one type at least `unsigned`". `(a + b) < a` insufficient for `unsigned char` – chux - Reinstate Monica May 08 '19 at 01:40
  • @chux, "[...] reports correctly on whether the sum overflows the wider of their types ***or unsigned int*** (whichever is wider)." – John Bollinger May 08 '19 at 10:46
8

Carry can be only 0 or 1. 1 if there was a wrapping-around and 0 otherwise. The wrapping-around is happening in case a + b > ULONG_LONG_MAX is true . Note, this is in mathematical terms, not in terms of C, as if a + b is actually overflowing, then this will not work. Instead you want to rearrange it to be a > ULONG_LONG_MAX - b. So the value of carry will be:

carry = a > ULONG_LONG_MAX - b ? 1 : 0;

or any preferred style equivalent.

  • Don't forget to include limits.h.
Eugene Sh.
  • 17,802
  • 8
  • 40
  • 61