萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 實現俄羅斯農民乘法算法

前言

俄羅斯農民乘法(Russian Peasant Multiplication)是一種古老的乘法算法,僅使用加法、除以 2、乘以 2 運算即可完成兩數相乘。本文介紹其原理並提供 PHP 遞歸實現。

算法原理

以 35 × 72 為例:

左列(不斷除 2,取整)右列(不斷乘 2)
3572
17144
8288
4576
21152
12304

規則:左列為奇數時,將右列對應數值累加。
72 + 144 + 2304 = 2520 = 35 × 72

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:判斷最低位是否為 1(即奇數)。
  • $m << 1:左移 1 位等價於乘 2。
  • $n >> 1:右移 1 位等價於整除 2。
  • 遞歸終止條件:$n == 0。

迭代版本(避免遞歸深度限制)

<?php
function russian_iterative($m, $n) {
    $res = 0;
    while ($n > 0) {
        if ($n & 1) $res += $m;
        $m <<= 1;
        $n >>= 1;
    }
    return $res;
}
?>

應用場景

教學演示、嵌入式系統無乘法指令環境、大整數乘法底層實現參考等。

copyright © 萬盛學電腦網 all rights reserved