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

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.

• Note that $(2^n-1)^3=(2^n-1)(2^n-1)^2=(2^n-1)(2^{2n}-2\cdot2^n+1)=(2^n-1)(2^{2n}-2^{n+1}+1)$. Oct 10, 2016 at 20:13

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$.)

• For the record, you need $1$ bit for $n = 1$ and $5$ for $n = 2$. Oct 10, 2016 at 21:24
• @RobArthan why does this argument fail for n<3. Oct 10, 2016 at 21:47
• @JamesDickens: you ought to try doing the calculations explicitly for yourself in those cases. Here's an explanation of what you will see if you do that: If $n = 2$, the first bit pattern on the right-hand side of Brian's first equation has a leading $0$. If $n = 1$, $2^{3n} - 3 .2^{2n}$ is negative and the calculation of the bit patterns on the right-hand side of the first equation doesn't handle negative numbers. Oct 10, 2016 at 22:02

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$).