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/
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz