如何编写计算功率的循环

我正试图在不使用pow()函数的情况下编写一个计算功率的循环。我纠结于怎么做。做base *= base甚至可以达到4的功率，所以有一些完全奇怪的事情我似乎无法理解。

int Fast_Power(int base, int exp){
int i = 2;
int result;
if(exp == 0){
result = 1;
}
if(exp == 1){
result = base;
}
else{
for(i = 2; i < exp; i++){
base *= base; 
result = base;
}
}
return result;
}

base *= base;

您的问题在于该语句，您根本不应该更改base。相反，您应该根据base的常数值来调整result。

要进行幂运算，您需要重复乘法，但base *= base会对该值进行重复squaring运算，因此您将获得比所需大得多的值。这实际上适用于四次方，因为您迭代4 - 2次，每次迭代求平方，然后是x⁴== (x²)²。

由于您迭代了6 - 2次和x⁶!= (((x²)²)²)²次，因此它对于像6这样的更高幂次是不起作用的。后一个值实际上相当于CCD_ 10。

顺便说一句(尽管你有争议)，实际上并不能保证适用于2的幂。如果您遵循这种情况下的代码，您将看到result从未被赋值，因此返回值将是任意的。如果它对你有效，那是偶然的，很可能会在某个时候咬到你。

您可以使用的算法应该类似于：

float power(float base, int exponent):
# 0^0 is undefined.
if base == 0 and exponent == 0:
throw bad_input
# Handle negative exponents.
if exponent < 0:
return 1 / power(base, -exponent)
# Repeated multiplication to get power.
float result = 1
while exponent > 0:
# Use checks to detect overflow.
float oldResult = result
result *= base
if result / base is not close to oldResult:
throw overflow
exponent -= 1
return result

该算法处理：

负积分指数(自x^-y=¹/_x^y以来)
CCD_ 13的未定义情形；以及
如果没有任意精度值，则会发生溢出(基本上，如果是(x * y) / y != x，则可以合理地确定发生了溢出)。请注意"不接近"的使用，由于精度限制可能会出现错误，因此检查浮点是否完全相等是不明智的——最好实现某种描述的"足够接近"检查

在转换为C或C++时，需要记住的一件事是，当使用最负的整数时，2的补码实现会引起问题，因为由于正值和负值之间的不平衡，其否定值通常再次相同。这可能会导致无限递归。

你可以简单地通过早期检测(在其他任何事情之前)来解决这个问题，比如：

if INT_MIN == -INT_MAX - 1 and exp == INT_MIN:
throw bad_input

第一部分检测2的补码实现，而第二部分检测INT_MIN作为指数的使用(有问题)。

您做错的是每次循环中的base *= base，每次迭代都会更改基础本身。

相反，您希望基数保持不变，并将最终结果乘以原始基数"exp"倍。

int Fast_Power(int base, int exp){
int result=1;
if(exp == 0){
result = 1;
}
if(exp == 1){
result = base;
}
else{
for(int i = 0; i < exp; i++){
result *= base;
}
}
return result;
}

您正在寻找的基本但天真的算法是：

int Fast_Power (int base, int exp)
{
int result = base;
if (exp == 0)
return result ? 1 : 0;
for (int i = 1; i < exp; i++) {
result *= base;
}
return result;
}

注意：result很容易溢出。您需要使用一些基本检查来防止整数溢出和未定义行为。

最小检查(请参阅：在两个大整数相乘期间捕获并计算溢出)可以合并如下。您必须在此处使用更宽的类型进行临时计算，然后将结果与INT_MIN和INT_MAX(在limits.h标头中提供)进行比较，以确定是否发生溢出：

#include <limits.h>
...
int Fast_Power (int base, int exp)
{
int result = base;
if (exp == 0)
return result ? 1 : 0;
for (int i = 1; i < exp; i++) {
long long int tmp = (long long) result * base;  /* tmp of wider type */
if (tmp < INT_MIN || INT_MAX < tmp) {           /* check for overflow */
fputs ("error: overflow occurred.n", stderr);
return 0;
}
result = tmp;
}
return result;
}

现在，如果您尝试，例如Fast_Power (2, 31);，则会生成一个错误并返回零。

此外，正如@paxdiablo在评论中所指出的，零的幂可能是未定义的，因为没有商定的值。如果您愿意，您可以添加一个测试并在这种情况下发出警告/错误。

首先，我同意使用base *= base可能是个错误。也就是说，这不一定是错误的。我的第一印象是OP试图像人类手动计算功率一样计算功率。例如，如果你想计算3^13，一个合理的方法是从计算2的幂的指数开始。

3^1=3
3^2=3*3=9
3^4=3^2*3^2=81
3^8=3^4*3^4=6561

然后您可以使用这些结果来计算3^13作为

3^13=3^1*3^4*3^8=1594323

一旦您了解了这些步骤，就可以对其进行编码。最困难的部分可能是确定何时停止对基数进行平方，以及哪些平方应该包含在最终计算中。也许令人惊讶的是，指数的(无符号)二进制表示告诉我们这一点！这是因为二进制中的数字表示二的幂，二者相加形成数字。考虑到这一点，我们可以写以下内容。

int Fast_Power(int base, int exp) {
int result = 1;
unsigned int expu = exp;
unsigned int power_of_two = 1;
while (expu > 0) {
if (power_of_two & expu) {
result *= base;
expu ^= power_of_two;
}
power_of_two <<= 1;
base *= base;
}
return result;
}

这段代码没有溢出保护，不过这是个好主意。坚持使用原始原型，它仍然接受负指数并返回整数，这是一个矛盾。由于OP没有指定溢出或负指数时应该发生什么，因此此代码不尝试处理这两种情况。其他答案提供了解决这些问题的合理方法。

相关内容

最新更新

热门标签：