面试题：C语言位运算实现高效乘法

Question

在C语言中，不使用乘法运算符 '*' ，仅通过位运算实现两个整数相乘的功能。请编写一个函数int multiply(int a, int b)来完成此任务，并简要说明你的思路。

Answer 1

#include <stdio.h>

int multiply(int a, int b) {
    int result = 0;
    while (b != 0) {
        if (b & 1) {
            result += a;
        }
        a <<= 1;
        b >>= 1;
    }
    return result;
}

思路说明

1. 初始化结果：将结果 result 初始化为0，这个变量将用于存储最终的乘积。
2. 循环判断：通过 while 循环，当 b 不为0时持续执行以下操作。
3. 判断最低位：使用 b & 1 来判断 b 的二进制表示的最低位是否为1。如果是1，说明 a 要累加到 result 中，因为这相当于在二进制乘法中，当当前位为1时，需要加上对应的 a 的倍数。
4. 移位操作：a <<= 1 将 a 左移一位，相当于 a 乘以2。b >>= 1 将 b 右移一位，用于检查下一位。
5. 返回结果：循环结束后，result 中存储的就是 a 和 b 的乘积，返回 result。