通過平方運算求冪（得到乘法運算的次數）

Question

我正在做作業，我必須用exponentiation by squaring來做兩件事。一個是獲得乘法的數量，另一個是獲得實際結果。

下面是一些例子：

2 
11 

應該輸出

2048 
5 

因爲2^11 = 2(2((2)²)²)²

我這樣做沒有遞歸和我得到的結果正確的，但數量乘法是錯誤的。如果我輸入2^6我得到3乘法，這是行，但如果我輸入2^8我得到4乘法，這是錯誤的。

你能指出我在做什麼錯誤，以獲得正確的乘法涉及？

下面是代碼：

public static void main(String[] args) { 
    double x, result = 1; 
    int n, multiplications = 0; 
    DecimalFormat df = new DecimalFormat("#.00"); 
    Scanner readLine = new Scanner(System.in); 

    x = readLine.nextDouble(); 
    n = readLine.nextInt(); 

    if (n == 1) { 
     multiplications++; 
     System.out.print(df.format(x) + "\n" + multiplications + "\n"); 
    } else if (n == 2) { 
     x *= x; 
     multiplications++; 
     System.out.print(df.format(x) + "\n" + multiplications + "\n"); 
    } else { 
     while (n > 0) { 
      if (n % 2 == 0) { 
       multiplications++; 
      } else { 
       multiplications++; 
       result *= x; 
       n--; 
      } 
      x *= x; 
      n /= 2; 
     } 
     System.out.print(df.format(result) + "\n" + multiplications + "\n"); 
    } 
} 

Answer 1

如果n % 2 == 0，你不繁殖;你只是方。所以請離開multiplications++。

然後2^8您可以：

n | n % 2 | multiplications 
---------------------- 
8 | 0  | 0 
4 | 0  | 0 
2 | 0  | 0 
1 | 1  | 1 

和1個乘法應該是正確的。由於2^8 = (((1² * 2)²)²)²

如果你想數平方的乘積，你應該做的

... else 
    multiplications = multiplications + 2 

而且事後減去2初始平方和乘法。

所以，總體來說：

while (n > 0) {  
    if(n % 2 == 1) { 
     multiplications++; 
     result *= x; 
     n--; 
    } 
    multiplications++; 
    x *= x; // shouldn't that be result *= result? 
    n /= 2; 
} 
multiplications -= 2; 

Answer 2

你應該看看是多少的二進制表示。 11的二進制表示形式爲1011.從左至右閱讀。對於每個新的二進制數字，將結果平方。然後對於每個1，乘以該因子。

爲2^11你這樣做：

第一個數字是1，所以2

下一個是零，所以只有方枘。4.

下一個是一個一個，所以平方4和乘以2. 4平方是16.時間2是32.

下一個是一個，所以正方形和乘法。 32的平方是1024.第二次是2048.