27、位操作与算法：用位运算实现乘法与除法（俄罗斯农民乘法）

说到用位运算做乘除法，很多人第一反应是「左移就是乘2，右移就是除2」。没错，但仅限于2的幂次。那如果我想算 a * 7 或者 a * 13 呢？难道只能调乘法器？

其实不然。今天我要跟你聊的，是一个古老但极其优雅的算法——俄罗斯农民乘法。它只用移位和加法，就能完成任意整数的乘法。我在做嵌入式驱动开发时，有一次需要在没有硬件乘法器的MCU上做音频算法，就是靠这个算法撑过去的。

俄罗斯农民乘法的原理

这个算法的思路很简单：
把其中一个数不断除以2（右移），另一个数不断乘以2（左移）。
当第一个数变成奇数时，就把第二个数累加起来。

说白了，就是利用了二进制展开的思想。举个例子：

计算 13 * 7：

a（不断除以2）	b（不断乘以2）	累加条件
13（奇数）	7	累加 7
6（偶数）	14	不累加
3（奇数）	28	累加 28
1（奇数）	56	累加 56
0	—	结束

结果：7 + 28 + 56 = 91。没错，就是 13 * 7。

为什么会这样？你想想看，13 的二进制是 1101，也就是 8 + 4 + 1。
7 * 13 = 7 * (8 + 4 + 1) = 7*8 + 7*4 + 7*1。
而 7*8 就是 7 左移3位，7*4 就是左移2位，7*1 就是不移位。
俄罗斯农民乘法，本质上就是在「检测二进制位是否为1」，然后累加对应的移位结果。

C语言实现

直接上代码。我个人习惯用 unsigned int，避免符号位带来的麻烦。

unsigned int russian_peasant_mul(unsigned int a, unsigned int b) {
    unsigned int result = 0;

    while (a > 0) {
        // 如果 a 是奇数，累加 b
        if (a & 1) {
            result += b;
        }
        // a 右移一位（相当于除以2）
        a >>= 1;
        // b 左移一位（相当于乘以2）
        b <<= 1;
    }

    return result;
}

这段代码很简洁。核心就三步：
1. 判断 a 的最低位是否为1。
2. 如果是，把当前的 b 加到结果里。
3. a 右移，b 左移。

我在项目中遇到过一个问题：如果 b 左移后溢出怎么办？嗯，这里要注意——这个算法只适用于无符号整数，而且你要确保 b 左移后不会超出 unsigned int 的范围。否则结果就错了。

用位运算实现除法

除法比乘法麻烦一点。俄罗斯农民乘法的思路反过来，就是除法：
把除数不断左移，直到接近被除数，然后做减法。

我直接给你看代码：

unsigned int russian_peasant_div(unsigned int dividend, unsigned int divisor) {
    if (divisor == 0) {
        return 0; // 除0错误，实际项目中应该做错误处理
    }

    unsigned int quotient = 0;
    unsigned int remainder = 0;

    // 从最高位开始处理
    for (int i = 31; i >= 0; i--) {
        remainder = (remainder << 1) | ((dividend >> i) & 1);

        if (remainder >= divisor) {
            remainder -= divisor;
            quotient |= (1 << i);
        }
    }

    return quotient;
}

这段代码的原理是：
从被除数的最高位开始，一位一位地往 remainder 里移。
一旦 remainder 大于等于除数，就减去除数，并在商的对应位上置1。

说白了，这就是我们手算除法时的「试商」过程，只不过用位运算实现了。

性能对比

你可能会问：这玩意儿比直接用 * 和 / 快吗？

答案是：看平台。

• 在带有硬件乘法器的 ARM Cortex-M4 上，直接用 * 更快。
• 但在一些低端 8 位 MCU（比如 8051、PIC）上，硬件乘法器很慢甚至没有，这时候俄罗斯农民乘法就派上用场了。
• 我记得有一次在 ATmega328 上做项目，乘法指令要 2 个时钟周期，但用移位加法实现的乘法只要 1 个周期——虽然代码长了点，但整体性能反而提升了。

平台	硬件乘法器	俄罗斯农民乘法	建议
ARM Cortex-M4	1~3 周期	几十个周期	用硬件乘法器
8051	无/很慢	较快	用位运算实现
RISC-V (无M扩展)	无	唯一选择	必须用位运算

避坑指南

我曾经在一个项目里用俄罗斯农民乘法做音频混音，结果声音有杂音。查了半天才发现：
我用的 int 是有符号的，移位操作导致了符号位扩展，结果全乱了。

知识体系图

下面这张图帮你理清俄罗斯农民乘法的核心逻辑：

这张图展示了俄罗斯农民乘法的完整循环：
判断 a 是否大于0 → 检查最低位是否为1 → 累加 → 移位 → 继续循环。

整个算法没有乘法指令，没有除法指令，只有移位、加法、位与。这就是它的魅力所在。

---

好了，关于俄罗斯农民乘法就聊到这里。这个算法虽然古老，但在嵌入式底层开发中依然有它的用武之地。下次你在没有硬件乘法器的芯片上做开发时，不妨试试它。

公众号:蓝海资料掘金营，微信deep3321