无算术/位运算、无循环实现两位二进制乘法：算法选型咨询

答案是不适合。

Booth算法的核心逻辑是通过循环遍历乘数的每一位，结合相邻位的差值决定对被乘数执行加减操作，本质依赖迭代流程。而题目明确禁止使用循环，若要强行实现无循环的Booth算法，必须手动硬编码每一位的处理逻辑——扩展到更多位数时，需要逐行添加对应位的判断和运算代码，完全违背了“易于扩展至更多位数”的要求。

既然要求模拟笔算乘法，我们可以把乘法拆解为部分积生成 + 多位数累加的逻辑，用函数封装每一步操作，既符合所有限制，又能轻松扩展位数。

核心思路 #

两位二进制数 m1m0 × n1n0 的笔算过程是：

1. 生成两个部分积：
   • 部分积1：n0 × m1m0（对齐最低位）
   • 部分积2：n1 × m1m0（左移一位，对齐次低位）
2. 将两个部分积累加，得到四位乘积 s3s2s1s0
3. 对因数和乘积做无前导零格式化输出

所有运算基于题目要求的add和carry函数，扩展到N位时，只需增加对应数量的部分积生成、移位操作，以及级联更多全加器即可。

代码实现框架（符合所有限制） #

基础函数（必须+辅助） #

// 无进位加两位二进制位
int add(int a, int b) {
    return (a != b) ? 1 : 0;
}

// 计算两位二进制位相加的进位
int carry(int a, int b) {
    return (a == 1 && b == 1) ? 1 : 0;
}

// 半加器：返回（和，进位）
pair<int, int> half_adder(int a, int b) {
    return {add(a, b), carry(a, b)};
}

// 全加器：处理带进位的三位相加，返回（和，进位）
pair<int, int> full_adder(int a, int b, int cin) {
    auto [sum1, carry1] = half_adder(a, b);
    auto [sum2, carry2] = half_adder(sum1, cin);
    int total_carry = (carry1 == 1 || carry2 == 1) ? 1 : 0;
    return {sum2, total_carry};
}

// 生成单一位的部分积：乘数位为1返回被乘数，否则返回00
pair<int, int> multiply_partial(int bit, int m1, int m0) {
    int p1 = (bit == 1) ? m1 : 0;
    int p0 = (bit == 1) ? m0 : 0;
    return {p1, p0};
}

// 格式化两位二进制数为无前导零的字符串
string format_two_bit(int bit1, int bit0) {
    if (bit1 == 1) {
        return bit0 == 1 ? "11" : "10";
    } else {
        return bit0 == 1 ? "1" : "0";
    }
}

// 格式化四位乘积为无前导零的字符串
string format_four_bit(int s3, int s2, int s1, int s0) {
    if (s3 == 1) {
        return to_string(s3) + to_string(s2) + to_string(s1) + to_string(s0);
    } else if (s2 == 1) {
        return to_string(s2) + to_string(s1) + to_string(s0);
    } else if (s1 == 1) {
        return to_string(s1) + to_string(s0);
    } else {
        return to_string(s0);
    }
}

主逻辑（两位乘法） #

int main() {
    // 输入示例："0110" → 被乘数01，乘数10
    string input = "0110";
    int m1 = input[0] - '0';
    int m0 = input[1] - '0';
    int n1 = input[2] - '0';
    int n0 = input[3] - '0';

    // 生成两个部分积
    auto [p11, p10] = multiply_partial(n0, m1, m0); // 部分积1：n0*m1m0
    auto [p21, p20] = multiply_partial(n1, m1, m0); // 部分积2：n1*m1m0（左移一位后为p21,p20,0）

    // 累加部分积得到四位乘积
    int s0 = add(p10, 0);
    int c0 = carry(p10, 0);

    auto [s1, c1] = full_adder(p11, p20, c0);
    auto [s2, c2] = full_adder(0, p21, c1);
    int s3 = c2;

    // 格式化输出
    string num1 = format_two_bit(m1, m0);
    string num2 = format_two_bit(n1, n0);
    string product = format_four_bit(s3, s2, s1, s0);

    cout << num1 << " × " << num2 << " = " << product << endl;
    // 输出示例：1 × 10 = 10
    return 0;
}

扩展性说明 #

当需要扩展到N位二进制乘法时：

1. 新增对应位数的format_n_bit函数
2. 生成N个部分积，每个部分积对应乘数的一位，左移对应位数
3. 用全加器级联实现N个部分积的累加（每一位的和由对应位置的部分积位加上低位进位计算）
   整个过程只需复用现有基础函数，无需修改核心逻辑，完全符合“易于扩展”的要求。

内容的提问来源于stack exchange，提问作者Immet09