booth 算法全称是布斯乘法算法，是计算机组成原理课程里面非常重要的补码乘法算法，主要用来实现带符号二进制数乘法运算，它最大特点就是可以直接处理补码形式的正负乘数，不需要单独区分正数和负数，也不用像传统原码乘法那样额外做符号位单独处理，通过扫描乘数相邻两位的编码变化，决定当前是做加法减法还是保持不变，相比普通移位累加乘法，booth 算法能够减少加法操作次数，提升带符号乘法的运算效率，广泛应用在 CPU 运算器 硬件乘法器设计当中，也是计算机考研和数字逻辑考试高频考点。
算法核心原理
booth 算法的设计思路是利用乘数补码里面连续的 1，把一串连续 1 转化成高位减低位加的形式，减少累加次数。算法需要设置一个附加位 y 负 1，初始值为 0，每次取乘数最低位和附加位组成两位，根据这两位的组合判断操作。
两位编码对应的操作规则表格
表格
| y i y 负 1 | 操作含义 | 执行动作 |
|---|---|---|
| 0 0 | 连续 0 | 部分积不变，算术右移一位 |
| 0 1 | 上升沿 | 部分积加上被乘数补码，再算术右移一位 |
| 1 0 | 下降沿 | 部分积减去被乘数补码，再算术右移一位 |
| 1 1 | 连续 1 | 部分积不变，算术右移一位 |
运算执行步骤
第一步 初始化，设置部分积初始值为 0，位数扩展到和被乘数相同长度，乘数保持补码形式，附加位 y 负 1 置 0。
第二步 循环判断，每次读取当前最低位 yi 和附加位 y 负 1，按照上表执行加法减法或者保持不变。
第三步 执行算术右移，部分积和乘数联合一起算术右移，同时把 yi 移动到附加位 y 负 1 位置。
第四步 重复循环，循环次数等于乘数的位数，全部轮次结束之后，部分积高位加上乘数低位，拼接得到最终补码乘积。
算法特点
优点，支持带符号补码直接运算，正负乘数统一一套流程，连续长串 1 的时候可以减少加法次数，硬件实现逻辑规整。
缺点，基础版本是两位 booth，每次只判断相邻两位，还有改进的高位编码版本也就是基 4booth 算法，一次判断三位，进一步减少循环次数，但是硬件电路复杂度会上升。
注意，booth 算法里面移位必须使用算术右移，不能使用逻辑右移，算术右移会保留符号位，这是带符号运算的关键，如果错用逻辑右移结果就会出错。
应用场景
booth 算法主要集成在 CPUALU 运算单元，硬件乘法器，单片机 DSP 芯片里面，软件层面一般不会手动编写，大多是硬件电路实现，教材里面重点讲解它的编码规则 运算流程 例题计算，考试经常出计算题，要求手写 booth 算法完整运算表格。
综合来说 booth 算法就是一套补码带符号乘法的编码运算方案，依靠相邻两位编码判定加减移位，统一正负乘数运算流程，是计算机硬件乘法设计的经典算法。
【相关 FAQ】
问题 1 booth 算法是原码乘法吗
回答 1 booth 算法不是原码乘法，booth 算法是补码乘法算法，专门处理带符号补码乘数，不需要单独处理符号位，和原码乘法运算逻辑不一样。
问题 2 booth 算法为什么要设置附加位
回答 2 booth 算法设置附加位 y 负 1，是为了让最低位可以和初始 0 组成两位编码，保证第一轮判断可以正常执行，是 booth 算法初始化必备设置。
问题 3 booth 算法移位为什么要用算术右移
回答 3 booth 算法运算过程必须使用算术右移，因为 booth 算法处理补码带符号数，算术右移保留符号位，逻辑右移会破坏符号位，造成 booth 算法最终乘积出错。
问题 4 基 4booth 算法和普通 booth 算法区别
回答 4 普通 booth 算法是两位编码，基 4booth 算法属于改进版 booth 算法，一次判断三位编码，减少循环迭代次数，硬件复杂度相比基础 booth 算法更高。
【免责申明】
本内容仅为计算机学科科普介绍，算法细节会根据教材版本略有差异，学习备考请以指定教材和课程讲义为准，不构成考试押题或者教学承诺。