The number of bits of a product of two decimal numbers

33 Views Asked by At

Theorem. Let us have two numbers $m,n\in\mathbb Z^+$ with $k$ and $l$ bits respectively where $k≥l$. Then $m\cdot n$ has either $k+l-1$ or $k+l$ bits.

Proof. Trivially follows from exponent rules. $$2^{k+l-2}=2^{k-l}\cdot 2^{l-1}≤mn<2^k2^l=2^{k+l}$$


According to this proof, it seems like $mn$ should actually have $k+l-1$ or $k+l-2$ bits... is there a mistake in this proof, or am I misunderstanding something? Where have I gone wrong?