CODEWITHSUNDEEP
c++bit-manipulation
newprint
newprint

Reputation: 7136

Binary Addition without overflow wrap-around in C/C++

I know that when overflow occurs in C/C++, normal behavior is to wrap-around. For example, INT_MAX+1 is an overflow.

Is possible to modify this behavior, so binary addition takes place as normal addition and there is no wraparound at the end of addition operation ?

Some Code so this would make sense. Basically, this is one bit (full) added, it adds bit by bit in 32 

int adder(int x, int y)
{
    int sum;
    for (int i = 0; i < 31; i++)
    {
        sum = x ^ y;
        int carry = x & y;
        x = sum;
        y = carry << 1;
    }

    return sum;
}

If I try to adder(INT_MAX, 1); it actually overflows, even though, I amn't using + operator.

Thanks !

Upvotes: 0

Views: 2958

Answers (3)

Jonathon Reinhart
Jonathon Reinhart

Reputation: 137398

What do you want the result of INT_MAX + 1 to be? You can only fit INT_MAX into an int, so if you add one to it, the result is not going to be one greater. (Edit: On common platforms such as x86 it is going to wrap to the largest negative number: -(INT_MAX+1). The only way to get bigger numbers is to use a larger variable.

Assuming int is 4-bytes (as is typical on x86 compilers) and you are executing an add instruction (in 32-bit mode), the destination register simply does overflow -- it is out of bits and can't hold a larger value. It is a limitation of the hardware.

To get around this, you can hand-code, or use an aribitrarily-sized integer library that does the following:

  • First perform a normal add instruction on the lowest-order words. If overflow occurs, the Carry flag is set.
  • For each increasingly-higher-order word, use the adc instruction, which adds the two operands as usual, but takes into account the value of the Carry flag (as a value of 1.)

You can see this for a 64-bit value here.

Upvotes: 1

Potatoswatter
Potatoswatter

Reputation: 137770

Overflow means that the result of an addition would exceed std::numeric_limits<int>::max() (back in C days, we used INT_MAX). Performing such an addition results in undefined behavior. The machine could crash and still comply with the C++ standard. Although you're more likely to get INT_MIN as a result, there's really no advantage to depending on any result at all.

The solution is to perform subtraction instead of addition, to prevent overflow and take a special case:

if ( number > std::numeric_limits< int >::max() - 1 ) { // ie number + 1 > max
    // fix things so "normal" math happens, in this case saturation.
} else {
    ++ number;
}

Without knowing the desired result, I can't be more specific about the it. The performance impact should be minimal, as a rarely-taken branch can usually be retired in parallel with subsequent instructions without delaying them.

Edit: To simply do math without worrying about overflow or handling it yourself, use a bignum library such as GMP. It's quite portable, and usually the best on any given platform. It has C and C++ interfaces. Do not write your own assembly. The result would be unportable, suboptimal, and the interface would be your responsibility!

Upvotes: 4

nerozehl
nerozehl

Reputation: 473

No, you have to add them manually to check for overflow.

Upvotes: 2

Related Questions