Integer Overflow
Have you ever encountered a situation where adding two positive numbers resulted in a negative number or vice versa? You see such ridiculous results when an overflow occurs with arithmetic operations. That is when the result of an arithmetic operation cannot be contained within the word size of the data type.
Let’s get this clarified with a few examples.
Unsigned Addition
Let’s say that we have two 4-bit numbers, 12 (in binary 1100) and 7 (in binary 0111). Sum of these two numbers, 12+7 = 19 (in binary 10011) needs 5 bits to represent the result. If we truncate the bits with weight greater than 2³ that is if we discard the higher order bit, we are left with 0011 which is 3. This is actually equivalent to the value 19 mod 16 = 3.
In C and Java, overflows are not considered as errors.
Two’s Complement Addition
Since both the positive and negative numbers can be represented with two’s complement, we have to decide what to do when the resulting value of a two’s complement addition becomes too large or too small to represent with a given number of bits. As we have seen here, with w bits,
When a sum of two numbers exceeds the max value, we call that a positive overflow and when the result is less than min value, we call it a negative overflow. Let’s see this in action with 4-bits.
The maximum positive value that can be represented with 4 bits in two’s complement representation is 7 and the minimum value is -8. Following table shows two examples of overflow scenarios.
Unsigned Multiplication
Just like with addition, in multiplication also we have to deal with overflow scenarios. For example with 4-bits to represent numbers 4 (in binary 0100) and 5(in binary 0101), multiplication (expected value 20[in binary 10100]) gives 4 (in binary 0100) as the result. This is equivalent to, 4.5 mod 2⁴ = 20 mod 16 = 4.
Two’s Complement Multiplication
With two’s complement numbers, we can derive the multiplication result in following two steps.
Let’s say we have two numbers x and y each with w-bits, then
