Checking overflow in C

Question

Let us have

int a, b, c; // may be char or float, anything actually
c = a + b;

let int type be represented by 4 bytes. Let's say a+b requires 1 bit more than 4 bytes (ie, let's say the result is 1 00....0 (32 zeroes, in binary)). This would result in C=0, and I am sure the computer's microprocessor would set some kind of overflow flag. Is there any built in method to check this in C?

I am actually working on building a number type that is 1024 bits long (for example, int is a built in number type that is 32 bits long). I have attempted this using unsigned char type arrays with 128 elements. I also need to define addition and subtraction operations on these numbers. I have written the code for addition but I am having problem on subtraction. I don't need to worry about getting negative results because the way I will call the subtracting function always ensures that the result of subtraction is always positive, but to implement the subtraction function I need to somehow get the 2's complement of the subtrahend, which is it self my custom 1024 bit number.

I am sorry if it is difficult to understand my description. If needed I will elaborate it more. I am including my code for the adding function and the incomplete subtracting function. the NUM_OF_WORDS is a constant declared as

#define NUM_OF_WORDS 128

Please let me know if you did not understand my question or any part of my code.

PS: I don't see how to upload attachments in this forum so I am directing you to another website. My code may be found there

click on download in this page

Incidentally, I found this I intend to replace INT_MAX by UCHAR_MAX as my 1024 bit numbers consist of array of char types (8-bit variable) Is this check sufficient for all cases?

Update:

Yes I am working on Cryptography.
I need to implement a Montgomery Multiplication routine for 1024 bit size integers.
I had also considered using GMP library but couldn't find out how to use it.
I looked up a tutorial and after a few small modifications I was able to build the GMP project file in VC++ 6 which resulted in a lot of .obj files, but now I am not sure what to do with them.
Still it would be good if I can write my own data types, as it will give me complete control over how the arithmetic operations on my custom data type work, and I also need to be able to extend it from 1024 bits to larger numbers in the future.

Answer 1

If you're adding unsigned numbers then you can do this

c = a+b;
if (c<a) {
  // you'll get here if and only if overflow has occurred
}

and you may even find that your compiler is clever enough to implement it by checking the overflow or carry flag instead of doing an extra comparison. For instance, I just fed this to gcc -O3 -S:

unsigned int foo() {
  unsigned int x=g(), y=h();
  unsigned int z = x+y;
  return z<0 ? 0 : z;
}

and got this for the key bit of the code:

movl  $0,   %edx
addl  %ebx, %eax
cmovb %edx, %eax

where you'll notice there's no extra comparison instruction.

Answer 2

Contrary to popular belief, an int overflow results in undefined behavior. This means that once a + b overflows, it doesn't make sense to use this value (or do anything else, for that matter). The wrap-around is just what most machines happen to do in case of overflow, but they might as well explode.

To check whether an int overflow will occur when adding two non-negative integers a and b, you can do the following:

if (INT_MAX - b < a) {
        /* int overflow when evaluating a+b */
}

This is due to the fact that if a + b > INT_MAX, then INT_MAX - b < a, but INT_MAX - b can not overflow.

You will have to pay special attention to the case where b is negative, which is left as an exercise for the reader ;)

Regarding your actual goal: 1024-bit numbers suffer from exactly the same overall issues as 32-bit numbers. It might be more promising to choose a completely different approach, e.g. representing numbers as, say, linked lists of digits, using a very large base B. Usually, B is chosen such that B = sqrt(INT_MAX), so multiplication of digits doesn't overflow the machine's int type.

This way, you can represent arbitrarily large numbers, where "arbitrary" means "only limited by the amount of main memory available".