爲什麼這種類型的電源功能起作用？

Question

res = 1; 
for (i = 1; i <= n; i <<= 1) // n = exponent 
{ 
    if (n & i) 
     res *= a; // a = base 
    a *= a; 
} 

這應該是更有效的代碼的權力，我不知道這是爲什麼工作。

for（）的第一行很好我知道爲什麼在那裏我< < = i。但我不明白這一行是：if（n & i）。我知道如何工作，但我不知道爲什麼...

Answer 1

讓我們說你有一個無符號數字的二進制表示。你如何找到十進制表示？

讓我們舉一個簡單的四位例如：

N = | 0  | 1 | 0 | 1 | 
    ----------------------------------------- 
    | 2^3 = 8 | 2^2 = 4 | 2^1 = 2 | 2^0 = 1 | 
    ----------------------------------------- 
    | 0 |  4 | 0 |  1 | N = 4 + 1 = 5 

現在，如果基礎沒有被固定爲2的每一位的反而是前一位的平方會發生什麼，你乘的貢獻從每一位的，而不是添加：

N = | 0 | 1 | 0 | 1 | 
    ---------------------------- 
    | a^8 | a^4 | a^2 | a^1 | 
    ---------------------------- 
    | 0 | a^4 | 0 | a^1 | N = a^4 * a^1 = a^(4+1) = a^5 

正如你看到的，代碼計算^ N