[Solved]: Number of digits in a binary product

I assume you want to know the maximum possible bits that a product of two numbers might have. Under that assumption, let the first number $a$ have $m$ bits, and the second number $b$ have $n$ bits. Then, $$a leq 2^{m} – 1 $$ Similarly, $$b leq 2^{n} – 1$$ Then, the product is: $$a cdot b leq 2^{m+n} – 2^m – 2^n + 1$$ Now, both $2^m$ and $2^n$ are greater than $1$ (since $n, m > 0$). So, $$a cdot b < 2^{m+n} – 1$$ Therefore, at most $m+n$ bits are sufficient for the product of the two numbers. Of course, lesser bits might suffice. Also, the sign bit is not included in the computation, and each of $a$, $b$, and $a cdot b$ might have a separate sign bit. If you really need to optimize on space, you can check $a$ and $b$ for special cases. Some cases could be:

• $a$ or $b$ is $0$: You need 1 bit
• $a$ or $b$ is $1$: You need as many bits as the other number
• One of the numbers is a power of $2$: It will contain exactly one $1$, say at position $i$ (LSB is position 0). Then, the multiplication is equivalent to left shifting the other number by $i$ bits.

You might think up other special cases if you really need to. Edit: As pointed out by Sam in the comments, if you impose the restriction that the most significant bit has to be 1 (unless the number itself is 0), you can get a lower bound too. Since the MSB is 1, we have: $$a geq 2^{m-1}$$ and $$b geq 2^{n-1}$$. Thus, $$a cdot b geq 2^{m + n – 2} = 2^{(m+n-1) – 1}$$ To represent $2^{(m+n-1)-1}$, you require $m+n-1$ bits, and so to represent $a cdot b$, you need at least $m+n-1$ bits. This leaves the special case when either of the numbers is $0$, and assumes there are no leading 0’s in any of the numbers. As a conclusion, if you know the number of binary digits/bits of your number (as you mention in your question), you are most likely implying that there are no leading $0$’s and the left-most bit is $1$ (exception being when the number itself is 0, where you can simply assign 1 bit for the resulting product). In such a scenario, the product will have either $m+n$ bits or $m+n-1$ bits.