# Booth 算法

这里写点什么捏？就先来点简介吧！！比较法是 Booth 夫妇先提出来的，也称 booth 算法。

那么！！咱们怎么解题呢，不要担心，其实 booth 算法非常简单，不要被长长的算式所迷惑鸭！！

接下来就由我来简单快速的叙述一下如何利用 booth 算法去做题！

# 准备开始！

首先题目里一般会这样给：已知 [x] 补 = xxxxx，[y] 补 = xxxxx，利用 booth 算法求解 [x*y]。

booth 算法的符号位是成双成对的，和你不一样，因为你还没有成双成对哈哈哈哈哈哈（不是）

另外，我们还需要额外记住的四个固定形态：

尾数形态	作法
00	右移一位
01	+[x] 补 后 右移一位
10	+[-x] 补后 右移一位
11	右移一位

# 例题一

已知 [x] 补 = 0.0101，[y] 补 = 1.0101，利用 booth 算法求解 [x*y]

做题前我们需要做一些准备，首先我们写出双符号位形态的 [x] 补、[-x] 补以及 [y] 补（无需双符号）

• [x] 补 = 00.0101

• [-x] 补 = 11.1011

• [y] 补 = 1.0101

然后列出如下表格：

部分积	乘数	辅助
		0

我先写到这，如果有想先试试的小伙伴可以先按照自己的思路去写，还没记起来的的小伙伴们可以继续往下看，一会我还会写出两道例题供大家去练习。

解答开始！

辅助位置默认为 0，乘数就是 [y] 补 = 11.0101，部分积初始值也为 0.

	部分积	乘数	辅助
	00 0000	1010 1	0	一次判断
10 还记得加什么嘛？没错就是加 [-x] 补 +	11 1011
=	11 1011
右移	11 1101	1101 0	1	二次判断
01 还记得加什么嘛？没错就是加 [x] 补 +	00 0101
=	00 0010
右移	00 0001	0110 1	0	三次判断
10 还记得加什么嘛？没错就是加 [-x] 补 +	11 1011
=	11 1100
右移	11 1110	0011 0	1	四次判断
01 还记得加什么嘛？没错就是加 [x] 补 +	00 0101
=	00 0011
右移	00 0001	1001 1	0	五次判断
10 还记得加什么嘛？没错就是加 [-x] 补 +	11 1011
	11 1100

OK 兄弟们，小数点后有四位，那么我们需要进行五次判断，现在已经完成计算过程了，答案已经呼之欲出了！！

[x*y] = 1.1100 1001（如果要双符号为就这样去写：[x*y] = 11.1100 1001）

总结一下，辅助位配合乘数最后一位作判断操作，00 和 11 只需右移就好，而 01 要 +[x] 补，11 要 +[-x] 补，这样我们就能得到最终的结果了。

接下来再来一道爽题！！！

# 例题二

已知 [x] 补 = 1.0101，[y] 补 = 1.0011，利用 booth 算法求解 [x*y]

老规矩：

• [x] 补 = 11.0101
• [-x] 补 = 00.1011
• [y] 补 = 1.0011

列表：

	部分积	乘数	辅助
	00 0000	10011	0	一次判断
10 +	00 1011
=	00 1011
右移	00 0101	1100 1	1	二次判断
11 右移	00 0010	1110 0	1	三次判断
01 +	11 0101
=	11 0111
右移	11 1011	1111 0	0	四次判断
00 右移	11 1101	1111 1	0	五次判断
10 +	00 1011
	00 1000

第五次判断后无需移动

答案：0.1000 1111

怎么样，是不是非常爽，在五次判断中出现了两次数字相同的情况，这时候我们只需要进行右移，无需进行计算。

最后我在给大家一道练习题，自己练习一下叭～～～

# 练习

已知 [x] 补 = 0.1101，[y] 补 = 0.1011，利用 booth 算法求解 [x*y]

部分积	乘数	辅助
		0

# 鸣谢

感谢 B 站 up 主制作的视频，真的非常不错