Let x y and z be three integers Suppose that the binary repr

Let x, y and z be three integers. Suppose that the binary representation of x uses n bits, the binary representation of y uses n bits and the binary representation of z uses n bits. How many bits does the binary representation of the product xyz use?

Solution

The binary representation of x uses n bits so there are 2^n possibilities for the value of x. The same is true for y and z.

So in total for multiplcation we have to deal for (2^n)*(2^n)*(2^n) possibilities. Total there are 2^3n possibilities. So we should use 3n bits for product.