2

If I multiplie two 16-bit numbers, the result will be 32-bit long. But why is this so? What is the clear explanation for this?

And for my right understanding: The calculation for this is: n-bit number multiplied with a m-bit number gives a (n+m) bit number?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
user3146246
  • 55
  • 2
  • 8
  • It is up to the processor designer how they want to handle multiplication. Some choose to return a truncated single-precision result. Others return a full double-precision result. – Raymond Chen Jan 28 '14 at 21:06
  • This is not the answer which i searched for. This rule is not only for assembly or computers. A Math-Example: The multiplie of two numbers (each number has 2 digits) gives a result-number with 4 digits. But why? I search a clean, logical explanation for this. – user3146246 Jan 28 '14 at 21:13
  • 7
    This is a math question, not a programming question. "Why does multiplying two two-digit numbers result in a four-digit number?" Try http://math.stackexchange.com/ – Raymond Chen Jan 28 '14 at 21:35
  • "And for my right understanding: The calculation for this is: n-bit number multiplied with a m-bit number gives a (n+m) bit number?" So what do you get when m=16 and n=16? – turboscrew Jan 29 '14 at 10:58

2 Answers2

6

(2n - 1)*(2m - 1) = 2n+m - 2n - 2m + 1

-(2n + 2m) is like clearing the bits at index n and m, which does not affect much the result compared to 2n+m, so you need n+m bits to represent the result.

For example 11112*11112 = 111000012 (15*15 = 225)

In general, (bn - 1)*(bm - 1) = bn+m - bn - bm + 1, so multiply an n-digit by an m-digit number in an arbitrary base b results in a number at most n+m digits

You can see that easily in base 10: 9*9 = 81 (1 digit * 1 digit = 2 digit) or 99*99 = 9801 (2 digit * 2 digit = 4 digit)

phuclv
  • 37,963
  • 15
  • 156
  • 475
0

For simplicity, let's take unsigned binary numbers. With n binary digits, you can represent 2^n different numbers, ranging from zero upto 2^n-1. When multiplying an n-digit binary number with an m-digit binary number, the result will be a number between zero and (2^n-1) * (2^m-1) = 2^(n+m) - 2^n - 2^m + 1, which typically is only marginally less than 2^(n+m)-1. To represent such a range of results, you need n+m binary digits.

Ruud Helderman
  • 10,563
  • 1
  • 26
  • 45