Multiply 16-bit integers using 8-bit multiplier

Given two 16-bit positive values stored in 32-bit integer variables, find the product using the 8-bit multiply operator that that takes two 8-bit numbers and returns a 16-bit value.

 
The idea is to divide the given 16-bit numbers (say m and n) into 8-bit numbers first (say mLow, mHigh & nLow, nHigh). Now the problem is reduced to something similar to multiplication of a 2-digit number with another 2-digit number. For example,
 

                                   [mHigh mLow]    X
                                   [nHigh nLow]
                                   —————————————-
                    [mHigh * nLow] [mLow * nLow]
    [mHigh * nHigh] [mLow * nHigh]
——————————————————————————————————————————————————————————————–
[mHigh * nHigh] + [mLow * nHigh + mHigh * nLow] + [mLow * nLow]
——————————————————————————————————————————————————————————————–

 

In the solution below, we are using unsigned char to represent a 8-bit number and unsigned short to represent 16-bit number.
 
C++ implementation –
 

Download   Run Code

Output:

23472 in binary is 0101101110110000
2600 in binary is 0000101000101000

Normal multiplication m * n = 61027200
Using 8-bit multiplier m * n = 61027200

 
References: https://ccrma.stanford.edu/~hugo/cs/

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of