什麼是尋找二進制值的最佳算法方式，其中基礎和功率都是二進制的？

Question

假設問題是1010^1110，那麼怎麼算出一個最快的解決方案呢？

我得到了這樣的製劑（（1010^2）^ 2）^ 2 *（1010^2）^ 2 * 1010^2

Answer 1

十進制權力

您可能想擴展您以2的冪數這將是可能的，因爲任何自然數可以爲2。例如功率和擴展，你可以使用：

function getPowersOf2($number) 
{ 
    if(!$number) 
    { 
     return []; 
    } 
    $p = floor(log($number, 2)); 
    return array_merge([$p], getPowersOf2($number-pow(2, $p))); 
} 

-to生成序列。對於14，它將是8 + 4 + 2，所以2^3 + 2^2 + 2^1，結果是[3, 2, 1]。然後，你就可以使用此類似：

function getPower($base, $number) 
{ 
    $result = 1; 
    foreach(getPowersOf2($number) as $pow2) 
    { 
     $temp = $base; 
     while($pow2--) 
     { 
     $temp*=$temp; 
     } 
     $result*=$temp; 
    } 
    return $result; 
} 

- 所以每個功率將產生最終的表達一個乘法各倍增也將產生一個乘法。例如，如果原始動力是14，這將是8操作，因爲：

(x^14) = x^(8+4+2) = x^(2^3+2^2+2^1) = (((x^2)^2)^2)*((x^2)^2)*(x^2) 

二元權力

這很難說，這是「優化」 - 看看getPowersOf2()功能 - 裏面有至少對數。但在你的情況下，你的力量已經轉換了。 1110意味着1*2^3 + 1*2^2 + 1*2^1 + 0 - 它是由基數定義。因此，你可以用很簡單的方式完成您的乘法：

function getPowerBin($base, $number) 
{ 
    $m = count($number)-1; 
    $result = 1; 
    foreach($number as $bin) 
    { 
     if($bin) 
     { 
     $temp = $base; 
     $pow2 = $m; 
     while($pow2--) 
     { 
      $temp*=$temp; 
     } 
     $result*=$temp; 
     $m--; 
     } 
    } 
    return $result; 
} 

- 所以你只是通過權力的二元演示（在我的情況陣列）迭代，並考慮當前電力$m - 得到相同的結果功能以上。

這可能是有用，因爲它會產生較少的乘法，但我懷疑它可以被稱爲優化 - 因爲它會使用內部的許多額外的東西。但就我們的基數增加多少倍而言 - 是的，它會贏。