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?
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.)
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):
signed int. But the reason I included the link was not so much because it directly answers the question (the article doesn't do that), but more because I thought it provides useful background as to why this question is interesting / relevant and why knowing the answer can be important.As other say:
unsigned int a, b, c;
c = (a + b) / 2;
a + b can be not representable in an unsigned int for some value of a and b.
A very similar situation led to a famous bug in the standard Java binary search implementation (binarySearch function).
See this famous Joshua Blosh blog post in 2006:
"Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Excerpts:
The bug is in this line:
6: int mid =(low + high) / 2;
further down:
So what's the best way to fix the bug? Here's one way:
6: int mid = low + ((high - low) / 2);
Note that in Joshua post, high is >= low and also int objects were used but Java treats signed overflow as wrapping. In C signed integer overflows are undefined behavior and unsigned wraparound.
It could cause overflow if a and b are high enough to yield an a + b higher than the maximum representable by an unsigned int.
If you only declare a variable in C without initialize it, it gets an unpredictably value. a and b can be some value which is currently at the adress they get in the memory.
You can debug C code in Eclipse CDT
http://www.eclipse.org/cdt/
With this IDE you can program in C anc C++ and it contains the GDB debugger.
http://www.gnu.org/software/gdb/
