求实数的整数次幂(循环版)(高效) (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;
}

运行结果：