Question

One possible performance enhancement is to do a shift and add instead of an actual multiplication. Since 9 × 6, for example, can be written (2 × 2 × 2 + 1) × 6, we can calculate 9 × 6 by shifting 6 to the left 3 times and then adding 6 to that result. Show the best way to calculate 0x33×0x55 using shifts and adds . Assume both inputs are 16-bit unsigned integers

Answer 1

Step1

Numbers are 0x33 and 0x55

33_hex= 3 x 16 + 3 = 51 =32 +16 + 3 = 2⁵ + 2⁴ + 2¹ +1 = 51

and

55_hex= 5 x 16 + 5 = 85 =64 +16 + 4 + 1 = 2⁶+ 2⁴ + 2² +1 = 51

Step2

It could be written as

33_hex X 55_hex = ( 2⁵ + 2⁴ + 2¹ +1) X 55_hex

Step 3

follow the below steps:

1. Set result = 0.
2. Shift 55_hex 5 times to the left and add it to the result.
3. Shift 55_hex 4 times to the left and add it to the result.
4. Shift 55_hex 1 times to the left and add it to the result.
5. Add 55_hex to the result.

Step 4

55_hex = (01010101)_two

assuming result is a 16 bit number

performing the above steps present in step 3

Steps	Add	Result
1	------	0000000000000000
2	101010100000	0000101010100000
3	10101010000	0000111111110000
4	10101010	0001000010011010
5	101010	0001000011101111

Step 5

Final result is:

(0001000011101111)_two = ( 10EF )_hex  

(0001000011101111)_two = ( 4335 )_ten  

Hence 0x33 × 0x55 = ( 10EF )_hex   = ( 4335 )_ten