Compute the minimum number of bits to store a * b + c -- NVIDIA

Problem

Assuming you have three N bit unsigned integers a, b and c, what is the min number of bits you would need to store the result of a * b + c?

Solution

The maximum of unsigned integer is 2^N - 1, so the maximum of a * b + c is (2^N - 1) * (2^N - 1) + 2^N - 1 = 2^2N - 2 * 2^N + 1 + 2^N - 1 = 2^2N - 2^N

The bit number is [log₂( 2^2N - 2^N)] = N + [log₂( 2^N - 1)] = 2N