How to debug the This C code

Question

While reading some question on a site I came across below question where a c question needs to be debug

unsigned int a, b, c;
/* a and b are assume to have some values */
c = (a + b) / 2; // <- There is a bug in this st
What is the bug? and how you debug it?

Some of the answer saying it could cause overflow(c=(a+b)/2).but really didn't get how it cause overflow?

Answer 1

a+b may overflow if the sum of a and b is larger than UINT_MAX, the maximum value for an unsigned int. E.g.,

unsigned a = 1;
unsigned b = UINT_MAX;

printf("%u\n", (a+b)/2);

prints 0.

If you want to find the average of two unsigned ints without overflow, do

c = a/2 + b/2 + (a % 2 & b % 2);

(or (a%2 + b%2)/2, or (a%2 && b%2), or ((a&1) & (b&1)), etc.)

Answer 2

If a and/or b are very large then a + b could exceed the maximum size of an unsigned integer (see MAX_UINT in the limits.h file). This would cause an overflow and so the result would be wrong. For example if a and b are both equal to 0x80000000 the result would be 0 in 32-bit arithmetic, rather than expected result 0x80000000.

To solve it you could use something like this instead:

c = a/2 + b/2 + (a % 2 == 1 && b % 2 == 1);

If you know that b is greater than a then you could use this slightly simpler version:

c = a + (b - a) / 2;

Read this article for information about how this bug appeared in binary search algorithms in may popular languages (though it talks about signed int rather than unsigned int):

• Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken