求实数的整数次幂(循环版)(高效)（位运算解题）

分手后的思念是犯贱 2024-03-31 09:36 114阅读 0赞

## 求实数的整数次幂(循环版)(高效) (10 分) ##

**原理图**：  
![在这里插入图片描述][a1e715ea5b2e49868498d5cb91b953a0.png]

请编写函数，用循环语句以最快的方法求任意实数的任意整数次幂。  
函数原型

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;
    }

**运行结果**：  
![在这里插入图片描述][c1514da293b7427e8499777a5f8bf44a.png]

[a1e715ea5b2e49868498d5cb91b953a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c4d4695bde8144db8e29cf063d4e6c7b.png
[c1514da293b7427e8499777a5f8bf44a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3dc0ac2c65b147b89e925446ca788c88.png