5

Possible Duplicate:
Best way to detect integer overflow in C/C++

If I have an expression x + y (in C or C++) where x and y are both of type uint64_t which causes an integer overflow, how do I detect how much it overflowed by (the carry), place than in another variable, then compute the remainder?

Community
  • 1
  • 1
Clark Gaebel
  • 17,280
  • 20
  • 66
  • 93

3 Answers3

10

The remainder will already be stored in the sum of x + y, assuming you are using unsigned integers. Unsigned integer overflow causes a wrap around ( signed integer overflow is undefined ). See standards reference from Pascal in the comments.

The overflow can only be 1 bit. If you add 2 64 bit numbers, there cannot be more than 1 carry bit, so you just have to detect the overflow condition.

For how to detect overflow, there was a previous question on that topic: best way to detect integer overflow.

Community
  • 1
  • 1
Himadri Choudhury
  • 10,217
  • 6
  • 39
  • 47
  • 1
    Agreed, and the simplest way to test for the overflow condition is that the result of the addition is < to one of the arguments exactly when there is an overflow. – Pascal Cuoq May 23 '11 at 02:03
  • Perfect, and fast too! Thanks. – Clark Gaebel May 23 '11 at 02:03
  • Oh, and how do I get the number as it "should be" after the overflow without actually overflowing the integer (which is undefined in C and C++)? – Clark Gaebel May 23 '11 at 02:05
  • 3
    @Clark Only signed overflow is undefined in C (probably the same goes in C++). Unsigned overflow is specified as giving the result modulo (largest representable integer + 1). – Pascal Cuoq May 23 '11 at 02:07
  • 3
    C99 6.2.5.9: "A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type." – Pascal Cuoq May 23 '11 at 02:12
  • @Pascal. Right. Well, I didn't read the standard either... but that's what wikipedia says: http://en.wikipedia.org/wiki/Integer_overflow – Himadri Choudhury May 23 '11 at 02:12
  • Signed overflow is undefined mainly for historical reasons -- there used to be machines that did 1s complement (vs 2s complement) signed arithmetic. I don't believe any current machines do this, and so signed arithmetic is predictable in practice, even though undefined in principle. – Hot Licks May 23 '11 at 02:31
  • 1
    @Daniel: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html – Clark Gaebel May 23 '11 at 02:37
  • @Daniel R Hicks: As the link in Clark Gaebel's comment implies, optimising compilers take advantage of this. If the reason had been only to support 1s complement and sign-magnitude machines, the standard would have specified it as implementation-defined rather than undefined (as with the bitwise operations on signed integers). – caf May 23 '11 at 05:30
3

For z = x + y, z stores the remainder. The overflow can only be 1 bit and it's easy to detect. If you were dealing with signed integers then there's an overflow if x and y have the same sign but z has the opposite. You cannot overflow if x and y have different signs. For unsigned integers you just check the most significant bit in the same manner.

Adam
  • 16,808
  • 7
  • 52
  • 98
  • 1
    Integer overflow is undefined in C and C++. If x + y overflows, z has an undefined value - not the remainder. – Clark Gaebel May 23 '11 at 02:06
  • Nvm I seem to have lied. Thanks! – Clark Gaebel May 23 '11 at 02:13
  • 1
    Signed integer overflow *is* undefined, which means that you have to detect it in advance and avoid the overflowing computation, just like you do with division by zero. With unsigned, you can safely detect it afterwards. – caf May 23 '11 at 05:32
0

The approach in C and C++ can be quite different, because in C++ you can have operator overloading work for you, and wrap the integer you want to protect in some kind of class (for which you would overload the necessary operators. In C, you would have to wrap the integer you want to protect in a structure (to carry the remainder as well as the result) and call some function to do the heavy lifting.

Other than that, the approach in the two languages is the same: depending on the operation you want to perform (adding, in your example) you have to figure out the worst that could happen and handle it.

In the case of adding, it's quite simple: if the sum of the two is going to be greater than some maximum value (which will be the case if the difference of that maximum value M and one of the operands is greater than the other operand) you can calculate the remainder - the part that's too big: if ((M - O1) > O2) R = O2 - (M - O1) (e.g. if M is 100, O1 is 80 and O2 is 30, 30 - (100 - 80) = 10, which is the remainder).

The case of subtraction is equally simple: if your first operand is smaller than the second, the remainder is the second minus the first (if (O1 < O2) { Rem = O2 - O1; Result = 0; } else { Rem = 0; Result = O1 - O2; }).

It's multiplication that's a bit more difficult: your safest bet is to do a binary multiplication of the values and check that your resulting value doesn't exceed the number of bits you have. Binary multiplication is a long multiplication, just like you would do if you were doing a decimal multiplication by hand on paper, so, for example, 12 * 5 is:

    0110
    0100
    ====
    0110
      0 
  0110  
    0   
  ++++++
  011110 = 40

if you'd have a four-bit integer, you'd have an overflow of one bit here (i.e. bit 4 is 1, bit 5 is 0. so only bit 4 counts as an overflow).

For division you only really need to care about division by 0, most of the time - the rest will be handled be your CPU.

HTH

rlc

rlc
  • 2,808
  • 18
  • 23