Question

Suppose you have 3 N-bit unsigned integers: a, b, and c. What is the minimum number of bits required to present: (a*b)+c in order not to get an overflow? Explain how you reached your answer.

Answer 1

Suppose you have 2 N-bit unsigned integers: a, b, c.

To find: Minimum number of bits required to present (a*b)+c, and no overflow should occur.

first perform a*b, here both numbers are N-bit long.

Maximum number of bits required to store multiplication of 2 n-bit numbers = n+n = 2n

Then add c ie (c*b)+c:

Here is the tricky part,

Maximum number that can be represented using N-bits = 2^N - 1

Maximum number in decimal that can be obtained by multipliying 2 N-bit numbers = ( 2^N-1 ) * ( 2^N-1 ) =

=> 2^2N - 2^N - 2^N +1 = 2^2N - 2^N+1 +1

Maximum number that can be represented using 2N bits = 2^2N -1 ....1

When we add another N-bit number in multiplication of 2 N-bit numbers,

Maximum number in decimal of (a*b)+c , all N-bit = 2^2N - 2^N+1 +1 + 2^N - 1 = 2^2N - 2^N

Which is less than what we can represent using 2N bits, see eq ...1

So minimum number of bits required to store (a*b)+c without getting overflow = 2N