How to judge an overflow when adding signed to unsigned

Question

I'm trying to detect the overflow when adding a signed offset to an unsigned position

uint32 position;
int32 offset;  // it could be negative
uint32 position = position+offset;

How can I check whether the result is overflow or underflow?

I have thought of an ugly way but not sure of its correctness.

• underflow: offset < 0 && position + offset >= position
• overflow: offset > 0 && position + offset <= position

And I'm also wondering if there's a more elegant way to do it.

Update:

What's the best solution if offset is long?

uint32 position;
long offset;  // it could be negative
uint32 position = position+offset;

Answer 1

Your test(s) is (are) correct. I don't see a more elegant way right now, perhaps there isn't.

Why the conditions are correct: arithmetic on uint32_t is arithmetic modulo 2^32. Conversion from int32_t to uint32_t is normally the reinterpretation of the bit-pattern (in any case, as @caf pointed out, it's reduction modulo 2^32 here, so it definitely works). Regard position and offset as arbitrary precision integers. Overflow happens if and only if
position + offset >= 2^32. But offset < 2^31, so position + offset < position + 2^31, which is less than position + 2^32, the next value that reduces to position modulo 2^32, so as uint32_t, then position + offset < position. On the other hand, if offset > 0 and position + offset < position, evidently overflow has occurred. Underflow happens if and only if position + offset < 0 as mathematical integers. Since offset >= -2^31, similar reasoning shows that underflow has occurred if and only if offset < 0 && position + offset > position.

Answer 2

The following function check for overflow/underflow when adding an int32_t to an uint32_t. It also contains some test cases as evidence of correctness.

#include <stdint.h>
#include <assert.h>

int is_overflow (uint32_t position, int32_t offset)
{
    if (offset > 0 && offset > UINT32_MAX - position) {
        // really we checked (offset + position > UINT32_MAX)
        // overflow
        return 1;
    }
    else if (offset < 0 && (uint32_t)offset <= UINT32_MAX - position) {
        // really we checked  (position + (uint32_t)offset <= UINT32_MAX)
        // the (uint32_t)offset maps negative offset to [2^31, UINT32_MAX]
        // underflow
        return -1;
    }

    // no over/underflow
    return 0;
}

uint32_t abs_of_negative_int32 (int32_t offset)
{
    assert(offset < 0);

    return ((UINT32_MAX - (uint32_t)offset) + 1);
}

int main (int argc, char *argv[])
{
    int r;

    r = is_overflow(0, 0);
    assert(r == 0);

    r = is_overflow(0, 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX - 1);
    assert(r == 0);

    r = is_overflow(0, INT32_MAX);
    assert(r == 0);

    r = is_overflow(0, -1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN + 1);
    assert(r == -1);

    r = is_overflow(0, INT32_MIN);
    assert(r == -1);

    r = is_overflow(UINT32_MAX, 0);
    assert(r == 0);

    r = is_overflow(UINT32_MAX, 1);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, 1);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - 1, 2);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(UINT32_MAX - INT32_MAX, INT32_MAX);
    assert(r == 0);

    r = is_overflow(UINT32_MAX - INT32_MAX + 1, INT32_MAX);
    assert(r == 1);

    r = is_overflow(abs_of_negative_int32(INT32_MIN), INT32_MIN);
    assert(r == 0);

    r = is_overflow(abs_of_negative_int32(INT32_MIN) - 1, INT32_MIN);
    assert(r == -1);

    return 0;
}