C++程序不使用乘法(*)和除法(/)操作符来找到幂

方法1（使用嵌套循环）:

我们可以通过重复加法来计算幂。

例如，计算5^6。

1）首先将5加5个，我们得到25. （5²）

2）然后将25加5次，我们得到125。（5³）

3）然后将125加5次，我们得到625（5^4）

4）然后将625加5次，我们得到3125（5^5）

5）最后将3125加5次，我们得到15625（5^6）

// C++ code for power function 
#include <bits/stdc++.h>
using namespace std;
  
//Works only if a >= 0 
//and b >= 0 
int pow(int a, int b) 
{ 
    if (b == 0) 
        return 1; 
    int answer = a; 
    int increment = a; 
    int i, j; 
    for(i = 1; i < b; i++) 
    { 
        for(j = 1; j < a; j++) 
        { 
            answer += increment; 
        } 
        increment = answer; 
    } 
    return answer; 
} 
  
//Driver Code
int main() 
{ 
    cout << pow(5, 3); 
    return 0; 
} 
  
//This code is contributed by rathbhupendra```

输出:

时间复杂度: O(a * b)

辅助空间: O(1)

方法2（使用递归）:

递归地添加a以获得两个数的乘积。递归乘以获得a的幂b。

// C++ program to implement 
// the above approach
#include<bits/stdc++.h>
using namespace std;
 
//A recursive function 
// to get x*y
int multiply(int x, int y)
{
    if(y)
        return (x + multiply(x, 
                y - 1));
    else
        return 0;
}
 
// A recursive function to get a^b
// Works only if a >= 0 and b >= 0
int pow(int a, int b)
{
    if(b)
        return multiply(a, 
                        pow(a, b - 1));
    else
        return 1;
} 
 
// Driver Code
int main()
{
    cout << pow(5, 3);
    getchar();
    return 0;
}
 
// This code is contributed by Akanksha Rai```

输出:

时间复杂度: O(b)

辅助空间: O(b)

方法3（使用位掩码）:

我们可以将a^n（假设为3^5）表示为3^4 * 3^0 * 3^1 = 3^，所以我们可以将5表示为其二进制即101

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Function calculating power
long long pow(int a, int n)
{
   int ans = 1;
    while(n > 0)
    {
        // Calculate last bit(right most) 
        // bit of n
        int last_bit = n&1;
         
        //if last bit is 1 then multiply 
        //ans and a
        if(last_bit)
        {
            ans = ans*a;
        }
        
        //Make a equal to square of a as on 
        //every succeeding bit it got squared 
        //like a^0, a^1, a^2, a^4, a^8
        a = a * a;
        n = n >> 1;
    }
    return ans;
}
 
// Driver code
int main() 
{
    cout << pow(3, 5);
    return 0;
}

时间复杂度: O(log n)

辅助空间: O(1)