C 語言面試題：用加法模擬乘法的隱藏 Bug

題目代碼

int func(int A, int B) {
    int C = 0, i;
    for (i = 0; i < B; i++) {
        C += C;   // Bug 在這裡
    }
    return C;
}

Bug 分析

• C 初始為 0，循環體 C += C 等價於 C = C * 2，永遠得到 0。
• 正確邏輯應為 累加被乘數 A：C += A;

修正版

int func(int A, int B) {
    int C = 0;
    for (int i = 0; i < B; i++) {
        C += A;   // 關鍵修正
    }
    return C;
}

進階優化（俄羅斯農民算法 / 移位加法）

int multiply(int a, int b) {
    int res = 0;
    while (b > 0) {
        if (b & 1) res += a;
        a <<= 1;
        b >>= 1;
    }
    return res;
}
// 時間複雜度 O(log b)，適合無乘法指令的嵌入式場景

面試加分點

1. 指出 溢出風險：題目雖說不考慮，但實際工程需用 long long 或檢查 INT_MAX。
2. 討論 負數處理：補碼下移位算法需轉無符號或單獨處理符號位。
3. 提及 編譯器優化：現代 GCC/Clang -O2 會將乘法直接降級為移位加法指令序列。