Question

You know that to multiply a binary integer by 16, all you have to do is shift the value over by 4 bit positions -- which in hardware can literally be done without a function unit simply by connecting bus wires such that bit k goes to position k+4 and positions 0-3 are connected to ground. Well, it's harder to multiply by 15. However, by using Booth's algorithm, a single 32-bit add/subtract ALU is sufficient to implement multiply of a 32-bit number by 15 as a fast combinatorial circuit. Explain how this would be done by giving a formula for X*15 as a C expression (for example, X*5 would be (X<<2)+X).

Answer 1

To find X*15
it can be written as (X*16 - X)
shift the value X left by 4 and subtract X from it.
C expression
X = (X << 4) - X