NVIDIA Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
It'd be
log(2){((2^N) - 1)((2^N) - 1) + ((2^N) - 1)}
= log(2) {2^2N - 2^N}
Leaving away -2^N, since we are looking for the highest number of bits,
we get
= log(2) {2^2N}
= 2N
another way of thinking:
for a * b, if b is a (N+1) bit unsigned integer, a * b means shift variable a N bits left, which results in a 2*N bit. And it's obvious that is reachable for a * b, since if a is the maximum digit for an N-bit integer, and b is 10...0(N zero following 1 one), then a * b is not the smallest 2*N-bit number
Another easy way to understand this is : consider N to be 8 bits or 1 byte... An unsigned int of 1 byte can have a max value of 255. Now applying the given equation with the maximum values possible:
a*b + c = 255*255 + 255 = 65280
we know unsigned 8 bit value max is 255 . Similarly unsigned 16 bit value is 65536 and 65280 is less than 65536. Hence we need 16bits for storing the result or 2N bits.
also, what matters more is how you work throught the answer, not just come up with some fancy equation. Consider:
111*111 + 111 = 111 * (111 + 1)
The term in parentheses is at most N+1 bits and not greater than 2^(N+1) so it can shift by at most N bits. It turns into a simple shift by N bits, so the answer is 2N
2N
- Anonymous October 20, 2012This is how i calculated
(2^N-1)(2^N-1) + 2^N-1 = (2^2N - 1) - (2^N-1)