I have 2's Complement digit range from negtive to positive. How to multiply it with a constant?
Now, I have to turn 2's complement to signed-digit format and do shift-addition/multiplication.
And there is a big problem confused me a long time:
Is there any method have the merits from signed-digit(easy to multiply) and 2's complement(easy to add)?
Any suggestions will be appreciated!
Best regards,
Davy
You should use booth's algorithm or Modified Booth algorithm. See the following links:
1) **broken link removed**
2) userpages.umbc.edu/~padmanab/ fall03/cmpe415/BoothAlgo.pdf
You have to realize that you MUST use a proper data type for the result of multiplication so that it can FIT there:
e.g. you have to multiply numbers that fit into "signed char" type (i.e. into 1 byte with range from <-128 to +127>), then the maximum result is 16256 (absolute value) which can fit into "signed int" type (2 bytes with range <-32768 to 32767>)
Code:
signed int multiplier_1; // its value limited to <-128;+127> !
signed int multiplier_2; // its value limited to <-128;+127> !
signed int multiplication_result;
multiplication_result = multiplier_1 * multiplier_2; // this will give correct results
// for multipliers the multiplication of which
// won't exceed <-32768 to +32767>
for instance:
multiplier_1 = -128, i.e. number represented as 0xFF80 (two's complement of 128=> NOT(0x0080)+1 = 0xFF7F+1)
multiplier_2 = +127, i.e. number represented as 0x007F (your "constant")
multiplication_result = 0xFF80 * 0x007F = 0xC080
0xC080 is a negative number (MSBit=1), so that the result (its abs. value) is two's complement of it (with negative sign), i.e. NOT(0xC080)+1 = 0x3F7F+1 = (-)0x3F80 = (-)16256 = -128*127