二进制乘法
补码与真值的转换公式
记X为有符号数，[X]补 =
X =
补码的乘法规则
先考察两个补码乘法运算的例子
记[X]补 =
可以验证，当X，Y均为正数或者无符号数时，有 [X Y]补 = [X]补 [Y]补
若乘数为负数，负数的符号位参加运算，使得得到的结果出现偏差。因此在加数相加时还需要进行特判。
Booth算法
从竖式出发
回忆算术中，竖式计算乘法的过程。
考虑XY，X 1 = X，X * 0 = 0，乘数后得到的结果位移后相加得到积。所以考虑如何能通过变化使得某个乘数二进制表达形式里1的数量尽量少。首先考虑一个1，即 010(B) 1的数量不能再少了，不变。再考虑多个1连在一起的情况，如 01110(B) = 01000(B) - 00010(B) 。我们可以从高位开始研究这种字符串的特征（对当前位进行操作，操作类型和当前位和前位有关）。如下表。
| 字符串特征 | 操作 | 一点补充 |
|---|---|---|
| 00 | 无 | 低位为0，不需要加 |
| 01 | 加上X | 1序列的结尾0 |
| 10 | 减去X | 1序列的开始 |
| 11 | 无 | 在1序列里，不需要特殊处理 |
我们再考虑最低位，最低位前面没有位数，但是我们可以看成最低位是边界，所以可以补一个0辅助操作。
每次操作完之后都要进行移位。减去X可以看成加上X的相反数。即我们就可以化简乘法过程中的加法运算。但是请注意，计算相反数进行取反操作前要位数左对齐。
计算完之后结果应该为2n位，舍去溢出的2n高位。
从补码与真值之间的关系出发
记X，Y为有符号数，[X]补 =
则
由于是二进制，相邻两项的差的结果只能是-1，0，1，对应上表的减去X，无，加上X操作。真值和补码的关系对于有符号数，所以上述方法对有符号数也成立。
