Can somebody prove that when we add 2 bit integers and if there is an overflow then the result always will be lesser than the 2 operands used??
detecting 2 n bits integer addition overflow
2
$\begingroup$
arithmetic
-
3[Obligatory xkcd comic.](http://xkcd.com/571/) – 2010-12-06
2 Answers
3
Suppose $a$ and $b$ are the numbers you are adding. Suppose that $0 \le a,b < 2^n$. Then we must have that $a+b - 2^n < a$ and $a+b - 2^n < b$. Hence if overflow occurs the result is smaller than $a$ or $b$.
1
HINT $\rm\ \ \ a+b-c\ <\ a,b\ \iff\ a,b\ <\ c$