PHP 實作俄羅斯乘法演算法完整教學

什麼是俄羅斯乘法？

俄羅斯乘法（Russian Peasant Multiplication）是一種古老且高效的整數相乘演算法，又稱「埃及乘法」或「農民乘法」。其核心原理利用二進位分解，透過不斷將其中一個數字減半（捨去餘數）並將另一個數字加倍，最後將對應奇數行的加倍數相加，即可得到乘積。這種方法不需要背誦乘法表，只需會加倍、減半與判斷奇偶，非常適合電腦程式實作。

演算法步驟解析

以 35 × 72 為例：

1. 建立兩欄：左欄寫 35，右欄寫 72。
2. 左欄數字若為奇數，保留右欄數字；若為偶數，捨棄右欄數字。
3. 左欄數字持續除以 2（取整數），右欄數字乘以 2，直到左欄變為 1。
4. 將所有被保留的右欄數字相加，即為結果。

35   72   ← 奇數，保留 72
17  144   ← 奇數，保留 144
8   288   ← 偶數，捨棄
4   576   ← 偶數，捨棄
2  1152   ← 偶數，捨棄
1  2304   ← 奇數，保留 2304

結果：72 + 144 + 2304 = 2520，驗證 35 × 72 = 2520 正確。

PHP 程式碼實作

利用位元運算與遞迴，可用極簡潔的程式碼完成：

<?php
function russian($m, $n, $res = 0) {
    // 若 n 為奇數（最低位為 1），累加 m
    (1 == ($n & 1)) && $res += $m;
    // m 左移 1 位（乘 2），n 右移 1 位（除 2）
    $m = $m << 1;
    $n = $n >> 1;
    // 遞迴直到 n 為 0
    return $n ? russian($m, $n, $res) : $res;
}

echo russian(7, 8); // 輸出 56
?>

程式碼解析

• $n & 1：位元 AND 運算，判斷最低位是否為 1（即奇數）。
• $m << 1：左移一位，相當於乘以 2。
• $n >> 1：右移一位，相當於整數除以 2。
• 遞迴終止條件：$n 變為 0 時回傳累加結果 $res。

應用場景與優點

俄羅斯乘法在嵌入式系統、無硬體乘法器的處理器、或是教學示範二進位運算時非常實用。PHP 中雖內建乘法運算子，但理解此演算法有助於深入掌握位元運算與遞迴邏輯，也是演算法面試常見題目。