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

在C++中，使用乘法(*)和除法(/)操作符可以方便地计算幂。但是，如果你想编写一个C++程序，不使用乘法(*)和除法(/)操作符来找到幂，该怎么做呢？接下来，我们将介绍如何使用位运算符和递归来实现这个目标。

Bitwise Operators and Exponentiation by Squaring

首先，我们需要了解一些位运算符的基本概念。

位运算符操作数是整数类型，它们对每个位执行操作。以下是常见的位运算符：

&（按位与）：如果两个操作数中的相应位都为1，则将结果设置为1，否则将结果设置为0。
|（按位或）：如果两个操作数中的相应位中至少有一个位为1，则将结果设置为1，否则将结果设置为0。
^（按位异或）：如果两个操作数中的相应位不同，则将结果设置为1，否则将结果设置为0。
~（按位取反）：反转每个位（0变为1，1变为0）。
<<（左移位）：左移操作数的二进制表示。例如，x << y表示将x的二进制表示向左移动y个位置，并在右侧填充0。
>>（右移位）：右移操作数的二进制表示。例如，x >> y表示将x的二进制表示向右移动y个位置，并在左侧填充0。

使用这些运算符，我们可以实现指数平方。指数平方是一种计算幂的方法，它利用了指数的二进制表示，并以对数时间（O(log n)）的复杂度计算出幂。其原理如下：

将指数表示为二进制数字。
从左到右扫描二进制数字，如果当前位是1，则将基数乘以自身，否则将基数平方。
继续扫描，直到整个二进制数字扫描完毕。

下面是用C++实现指数平方的示例代码：

#include <iostream>

using namespace std;

int exp_by_squaring(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result *= base;
        }
        base *= base;
        exp /= 2;
    }
    return result;
}

int main() {
    int base = 2;
    int exp = 4;
    int result = exp_by_squaring(base, exp);
    cout << base << " to the power of " << exp << " is " << result << endl;
    return 0;
}

上述代码中，exp_by_squaring函数接受两个参数：base和exp。它使用while循环来扫描exp的二进制表示，根据指数的当前位数和在基数上的操作来更新结果。最后，当exp的所有位数都被处理完时，函数返回结果。

Recursion and Exponentiation

另一种实现幂的方法是递归。我们可以将问题分成两个部分：找到n/2的幂和执行乘法操作。直到基本情况（n等于1）被递归到，此时只需返回基数。

以下是一个使用递归计算幂的示例代码：

#include <iostream>

using namespace std;

int power(int base, int exp) {
    if (exp == 0) {
        return 1;
    }
    int result = power(base, exp / 2);
    if (exp % 2 == 0) {
        return result * result;
    } else {
        return base * result * result;
    }
}

int main() {
    int base = 2;
    int exp = 4;
   int result = power(base, exp);
    cout << base << " to the power of " << exp << " is " << result << endl;
    return 0;
}

上述代码中，power函数使用递归来计算幂。它首先检查基准情况，即exp是否为0。如果是，函数返回1。否则，函数递归调用自己来计算n/2的幂，并根据当前指数的奇偶性执行乘法操作。当exp等于1时，只需返回基数。