CODEWITHSUNDEEP
cpointersbitmultiplication
Utkarsh Kumar
Utkarsh Kumar

Reputation: 607

Multiplication of two 32 bit numbers using only 8 bit numbers

I saw this interview question online and can't find a good method other than the usual additive methods. Any suggestions if this can be done quicker using some bitshift / recursion or something similar ?

Upvotes: 1

Views: 2798

Answers (1)

Gavin Smith
Gavin Smith

Reputation: 3154

Bitshifting would be natural part of a solution.

To multiply a value a by an eight-bit value b, for each 1 bit in b, add up all the values of a multiplied by b with all other bits set to 0. For example, a * 10100001 = a * 10000000 + a * 00100000 + a * 00000001.

Taking this further, suppose we want to multiply 11001011 by 0010000, this is 11001011(bin) << 4(dec). Doing this on an eight-bit value gives you 10110000. You have also lost (8-4)=4 bits from the beginning. Hence you would also want to do 11001011(bin) >> 4(dec) to get 00001100 as a carry into the next "8-bit column" (assuming that we are using 8 columns to represent a 64-bit answer).

Recursion would not really be necessary. All you'd need is a loop through the 4 bytes of the first 32-bit number, with another loop through the 4 bytes of the second number inside, multiplying each pair of bytes together in turn and adding it to your solution.

Upvotes: 2

Related Questions