For 3 numbers represented with $n$ bits in binary, how many bits is required for their product.

Question

Problem:

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?

Thoughts:

My first impulse is to consider the case where $x,y,z$ are all the maximal number that can be represented by $n$ bits in binary, namely that $x=y=z=2^n -1 $.

Then $xyz = (2^n -1)^3 = 2^{3n}-2^{2n}-2^{2n+1}+2^{n+1}+2^n-1$

$=2^{2n}(2^n-1)-2^{n+1}(2^n-1)+2^n-1 = (2^{n}-1)(2^n-2^{n+1}+1)$

Expanding in this manner has not really helped me clarify what the solution should be. Any different approaches or hints would be much appreciated.

Answer 1

When you write out $(2^n-1)^3=2^{3n}-3\cdot 2^{2n}+3\cdot 2^n-1$ in binary, you get

$$\begin{align*} \color{crimson}{1\underbrace{00\ldots 00}_{3n}-11\underbrace{00\ldots 00}_{2n}}+\color{blue}{11\underbrace{00\ldots 00}_n-1}&=\color{crimson}{\underbrace{11\ldots 11}_{n-2}01\underbrace{00\ldots 00}_{2n}}+\color{blue}{10\underbrace{11\ldots 11}_n}\\ &=\underbrace{11\ldots 11}_{n-2}01\underbrace{00\ldots 00}_{n-2}10\underbrace{11\ldots 11}_n\;, \end{align*}$$

which has $3n$ bits. (I am assuming that $n\ge 3$.)

Answer 2

Note that

$$(2^n-1)^3\ge2^{3n-1}\iff\left(1-{1\over2^n}\right)^3 \ge{1\over2}$$

By Bernoulli's inequality (or simply by expanding the cube), we have

$$\left(1-{1\over2^n}\right)^3\ge1-{3\over2^n}\ge1-{3\over8}\gt{1\over2}\quad\text{if }n\ge3$$

Thus the maximum product of three $n$-bit numbers will have $3n$ bits if $n\ge3$. As noted in Rob Arthan's comment below Brian Scott's answer, if $n=1$ then $(2^n-1)^3=1$ has $1$ bit (not $3$), and if $n=2$ then $(2^n-1)^3=27=11011_2$ has $5$ bits (not $6$).