when two 16-bit signed data are multiplied, what should be the size of resultant?

Question

I have faced an interview question related to embedded systems and C/C++. The question is:

If we multiply 2 signed (2's complement) 16-bit data, what should be the size of resultant data?

I've started attempting it with an example of multiplying two signed 4-bit, so, if we multiply +7 and -7, we end up with -49, which requires 7 bits. But, I could not formulate a general relation.

I think I need to understand binary multiply deeply to solve this question.

Answer 1

First, n bits signed integer contains a value in the range -(2^(n-1))..+(2^(n-1))-1. For example, for n=4, the range is -(2^3)..(2^3)-1 = -8..+7

The range of the multiplication result is -8*+7 .. -8*-8 = -56..+64.

+64 is more than 2^6-1 - it is 2^6 = 2^(2n-2) ! You'll need 2n-1 bits to store such POSITIVE integer.

Unless you're doing proprietary encoding (see next paragraph) - you'll need 2n bits: One bit for the sign, and 2n-1 bits for the absolute value of the multiplication result.

If M is the result of the multiplication, you can store -M or M-1 instead. this can save you 1 bit.

Answer 2

This will depend on context. In C/C++, all intermediates smaller than int are promoted to int. So if int is larger than 16-bits, then the result will be a signed 32-bit integer.

However, if you assign it back to a 16-bit integer, it will truncate leaving only bottom 16 bits of the two's complement of the new number.

So if your definition of "result" is the intermediate immediately following the multiply, then the answer is the size of int. If you define the size as after you've stored it back to a 16-bit variable, then answer is the size of the 16-bit integer type.