# 一、while非递归

```#include <stdio.h>
double pow1(double x, unsigned int n)
{
int res = 1;
while(n--)
{
res *= x;
}
return res;
}
int main()
{
printf("2 ^ 10 = %f\n", pow1(2, 10));
printf("5 ^ 3 = %f\n", pow1(5, 3));
printf("10 ^ 0 = %f\n", pow1(10, 0));
return 0;
}```

```2 ^ 10 = 1024.000000
5 ^ 3 = 125.000000
10 ^ 0 = 1.000000```

# 二、递归方法1

```#include <stdio.h>
double pow2(double x, unsigned int n)
{
if(0 == n)
{
return 1;
}
if(1 == n)
{
return x;
}
return x * pow2(x, n - 1);
}
int main()
{
printf("2 ^ 10 = %f\n", pow2(2, 10));
printf("5 ^ 3 = %f\n", pow2(5, 3));
printf("10 ^ 0 = %f\n", pow2(10, 0));
return 0;
}```

# 三、递归方法2

```#include <stdio.h>
double pow3(double x, unsigned int n)
{
if(0 == n)
{
return 1;
}
if(1 == n)
{
return x;
}
if(n & 1)   // 如果n是奇数
{
// 这里n/2会有余数1，所以需要再乘以一个x
return pow3(x * x, n / 2) * x;
}
else        // 如果x是偶数
{
return pow3(x * x, n / 2);
}
}
int main()
{
printf("2 ^ 10 = %f\n", pow3(2, 10));
printf("5 ^ 3 = %f\n", pow3(5, 3));
printf("10 ^ 0 = %f\n", pow3(10, 0));
return 0;
}```

# 四、快速求幂算法

```#include <stdio.h>
double pow4(double x, int n)
{
double res = 1;
while (n)
{
if (n & 1)        // 等价于 if (n % 2 != 0)
{
res *= x;
}
n >>= 1;
x *= x;
}
return res;
}
int main()
{
printf("2 ^ 10 = %f\n", pow4(2, 10));
printf("5 ^ 3 = %f\n", pow4(5, 3));
printf("10 ^ 0 = %f\n", pow4(10, 0));
printf("3 ^ 19 = %f\n", pow4(3, 19));
return 0;
}```

```2 ^ 10 = 1024.000000
5 ^ 3 = 125.000000
10 ^ 0 = 1.000000
3 ^ 19 = 1162261467.000000```

# 五、效率比较

```#include <stdio.h>
#include <math.h>
#include <time.h>
using namespace std;
#define COUNT 100000000
double pow1(double x, unsigned int n)
{
int res = 1;
while(n--)
{
res *= x;
}
return res;
}
double pow2(double x, unsigned int n)
{
if(0 == n)
{
return 1;
}
if(1 == n)
{
return x;
}
return x * pow2(x, n - 1);
}
double pow3(double x, unsigned int n)
{
if(0 == n)
{
return 1;
}
if(1 == n)
{
return x;
}
if(n & 1)   // 如果n是奇数
{
// 这里n/2会有余数1，所以需要再乘以一个x
return pow3(x * x, n / 2) * x;
}
else        // 如果x是偶数
{
return pow3(x * x, n / 2);
}
}
double pow4(double x, int n)
{
double result = 1;
while (n)
{
if (n & 1)
result *= x;
n >>= 1;
x *= x;
}
return result;
}
int main()
{
int startTime, endTime;
startTime = clock();
for (int i = 0; i < COUNT; i++)
{
pow(2.0, 100.0);
}
endTime = clock();
printf("调用系统函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime));
startTime = clock();
for (int i = 0; i < COUNT/100; i++)
{
pow1(2.0, 100);
}
endTime = clock();
printf("调用pow1函数计算100万次，运行时间%d毫秒\n", (endTime - startTime));
startTime = clock();
for (int i = 0; i < COUNT; i++)
{
pow2(2.0, 100);
}
endTime = clock();
printf("调用pow2函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime));
startTime = clock();
for (int i = 0; i < COUNT; i++)
{
pow3(2.0, 100);
}
endTime = clock();
printf("调用pow3函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime));
startTime = clock();
for (int i = 0; i < COUNT; i++)
{
pow4(2.0, 100);
}
endTime = clock();
printf("调用pow4函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime));
return 0;
}```

```调用系统函数计算1亿次，运行时间187毫秒

# 六、math.h中的pow函数源码

```template<class _Ty> inline
_Ty _Pow_int(_Ty _X, int _Y)
{unsigned int _N;
if (_Y >= 0)
_N = _Y;
else
_N = -_Y;
for (_Ty _Z = _Ty(1); ; _X *= _X)
{if ((_N & 1) != 0)
_Z *= _X;
if ((_N >>= 1) == 0)
return (_Y < 0 ? _Ty(1) / _Z : _Z); }}```

# 七、结论

241 篇文章45 人订阅

0 条评论

## 相关文章

732

831

### 对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash到二叉树，从搜索到排序，从增加到删除......可以说，如果你理解了STL，你会...

2582

### 1012. 变换密码

1012. 变换密码 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 一密码变换规则如下：一...

3014

3515

7688

### Python数据分析(2)-pandas数据结构操作

pandas是一个提供快速、灵活、表达力强的数据结构的Python库，适合处理‘有关系’或者‘有标签’的数据。在利用Python做数据分析的时候，pandas是...

26110

1164

2040

### leetcode-78-子集（用bfs解决）

vector<vector<int>> subsets(vector<int>& nums)

4421