How do I detect unsigned integer overflow?

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

Similarly, you can estimate the maximum size of the result of a to the power of b like this:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.

You could also test for the possibility of overflow before you perform the multiplication:

if ( b > ULONG_MAX / a ) // a * b would overflow

If you have a datatype which is bigger than the one you want to test (say you do a 32-bit add and you have a 64-bit type), then this will detect if an overflow occurred. My example is for an 8-bit add. But it can be scaled up.

uint8_t x, y;    /* Give these values */
const uint16_t data16    = x + y;
const bool carry        = (data16 > 0xFF);
const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

It is based on the concepts explained on this page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

For a 32-bit example, 0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.

NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the parameters don't overflow as they are multiplied to get the final size.

The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.

You'll probably find that this is more efficient than doing the division as you've done in your example.

Oh, and it'll work in both C and C++ (as you've tagged the question with both).

Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:

FPE_INTOVF_TRAP Integer overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).

A bit of a shame really.

You can't access the overflow flag from C/C++.

Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv.

The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.

However, -ftrapv seems to do nothing on x86 using the latest GCC. I guess it's a leftover from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.

For unsigned integers, just check that the result is smaller than one of the arguments:

unsigned int r, a, b;
r = a + b;
if (r < a)
{
    // Overflow
}

For signed integers you can check the signs of the arguments and of the result.

Integers of different signs can't overflow, and integers of the same sign overflow only if the result is of a different sign:

signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
    // Overflow
}

Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 10⁸ — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.

You can't access the overflow flag from C/C++.

I don't agree with this. You could write some inline assembly language and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course, your code would no longer be portable to other architectures.

Look at info as and info gcc.

A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before performing the operations.

MSalter's answer is a good idea.

If the integer calculation is required (for precision), but floating point is available, you could do something like:

uint64_t foo(uint64_t a, uint64_t b) {
    double dc;

    dc = pow(a, b);

    if (dc < UINT_MAX) {
       return (powu64(a, b));
    }
    else {
      // Overflow
    }
}

Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.