求实数的整数次幂(循环版)(高效) (10 分)
原理图：
请编写函数，用循环语句以最快的方法求任意实数的任意整数次幂。
函数原型
double Power(double x, int n);
说明：参数 x 为底数，n 为指数。若参数正确，则函数值为 x 的 n 次幂。若参数不正确(当底数为 0 且指数为 0 或负数时无意义)，则报告错误，函数值为0。
提示：
指数 二进制 公式
1 0001 x=x
2 0010 x?2??=x?2??
3 0011 x?3??=x?x?2??
4 0100 x?4??=x?4??
5 0101 x?5??=x?x?4??
6 0110 x?6??=x?2???x?4??
7 0111 x?7??=x?x?2???x?4??
8 1000 x?8??=x?8??
9 1001 x?9??=x?x?8??
10 1010 x?10??=x?2???x?8??
11 1011 x?11??=x?x?2???x?8??
12 1100 x?12??=x?4???x?8??
13 1101 x?13??=x?x?4???x?8??
14 1110 x?14??=x?2???x?4???x?8??
15 1111 x?15??=x?x?2???x?4???x?8??
要求：不得调用 pow 函数，不得使用递归方法。
*/
// 这个位运算是大部分都不熟悉也不敢用的东西，但是确实是编程里面的一个非常重要的工具
#include <stdio.h>
#include <math.h>
double Power(double x, int n);
int main()
{
double x;
int n;
scanf("%lg %d", &x, &n);
printf("%g\n", Power(x, n));
return 0;
}
// 这个函数的原理就是吧指数转化为二进制，例如15，它的二进制就是1111,把每一个二进制数分开来看就是1000 + 100 + 10 + 1
// 转化为十进制就是8 + 4 + 2 + 1,当然计算的时候这个先后顺序是倒过来的1 + 2 + 4 + 8
// 然后这个循环次数就是4次原来的循环次数是15次，时间复杂度重O(n) 变成了O(log2 n),速度就是大幅度提高了
double Power(double x, int n) // 记住一定要double不然int再大都不够
{
double s = 1.0, p = x; // 这个s = 1.0必须这么写, 最开始p = x也没什么好说的，
int k = n;
if(0 == x) // 这个条件没什么好说的
{
if(n <= 0) // 增强代码的健壮性，包含了底数为0的时候，指数小于等于0的情况
{
s = 0.0;
printf("不正确的参数!\n");
}
else
{
s = 0.0;
}
}
else if(n > 0) // 另外两种情况的讨论
// 首先我们要知道一个常识1的补码是00000001，所以和1进行&（与运算） 之后结果就是看最后一位
// 原理很简单前面这个数字转化为二进制之后最后一位前面的不论是0还是1都会变成0，之后结果就只
// 能看最后一位了，这就是这个题的一个关键
{
while (k) // 循环k次就是
{
if(k & 1) // 进行与运行，看看是否s 是不是需要乘以p,例如指数为10,转化为二进制后位1010,可以分解为十进制2 + 8
// 真正运算的时候有两次是条件是成立的，
{
s *= p;
}
p *= p; // 在没有成立的时候p *= p的作用就是让这个p的值满足下一次条件需要的值（不太好解释，feel）
k >>= 1; // 然后右移1位，k的十进制数字/2（取整）,二进制数字例如1010变成0101
}
}
else if(n < 0)
{
s = 1.0 / Power(x, -n); // 题目说是没有用到递归但是为了争强题目的可读性，和简化代码还是用了点递归
}
return s;
}运行结果：
