C++快速幂算法

在使用C++进行幂运算时候,通常方法为

int a,b,sum=1;
cin>>a>>b;
for(int i=1;i<=b;i++)
{
     sum*=a;
}
cout<<sum;

这样的方法在进行较大数字的次方时需要循环b次,效率低,在刷题过程中会出现超时情况

所以,是否可以对该算法进行优化?

首先 以2的10次方为例

方法1:2^10=2^9*2=2^8*2*2=2^7*2*2*2..............................

方法2:2^10=4^5=16^2*4=256*4=1024

可见方法2在进行较多次方运算时效率更高

实现方法:

当求a的b次方时,b为偶数则将b除以2,同时将a平方

如:3^4=9^2=81^1

当b为奇数时则在原结果上乘上一次当前的a,同时对b减1

如:2^5==2^4*2

 

代码:

int a, b;
	unsigned long long int sum=1;
	cin >> a >> b;
	for (;b>0;)
	{
		if (b % 2 == 0)
		{
			a *= a;
			b /= 2;
		}
		else {
			sum *= a;
			b -= 1;
		}
	}
	cout << sum;

这样下来计算量会大幅减小

下面对代码进行优化:

首先判断奇数偶数时,通常方法为将该数字对2取模运算,结果为0则为偶数,当结果为1则为奇数

但更为简单的方法为将该数字对1进行“与运算”

例如:

4的二进制为:100

1的二进制为:1

对100和1进行与运算 得到结果为0,即可得出4为偶数

则可将“if (b % 2 == 0)”改为“if (b & 1 == 0)”

 

下面对b/=2进行优化

8的二进制为:1000

4的2进制为:100

2的二进制为:10

1的二进制为:1

由此可知,想要将b进行除以2的操作时,仅需将b进行右移1位操作

可将b /= 2;改为b >>= 1;

优化后代码如下

int a, b;
	unsigned long long int sum=1;
	cin >> a >> b;
	for (;b>0;)
	{
		if (b & 1 == 0)
		{
			a *= a;
			b >>= 1;
		}
		else {
			sum *= a;
			b -= 1;
		}
	}
	cout << sum;

 

点赞
  1. 胖虎说道:
    Google Chrome Android 10
    兄弟,咱俩一个学校的,不过不是一个学院的,我的专业并不是与计算机有关的,我现在已经大二了,之前大一的日子过的是浑浑噩噩,没有目标,到了大二,我终于有了自己的目标—就是做一个程序猿,但是对计算机,我只会玩游戏,对编程什么的相当于小白,我想从现在开始学习编程,但是不知道该从哪里下手,手忙脚乱的,所以希望能和你交流一下,给我提一些建议,您看可以嘛?
  2. 胖虎说道:
    Sogou Explorer Windows 10
    兄弟,咱俩一个学校的,不过不是一个学院的,我的专业并不是与计算机有关的,我现在已经大二了,之前大一的日子过的是浑浑噩噩,没有目标,到了大二,我终于有了自己的目标—就是做一个程序猿,但是对计算机,我只会玩游戏,对编程什么的相当于小白,我想从现在开始学习编程,但是不知道该从哪里下手,手忙脚乱的,所以希望能和你交流一下,给我提一些建议,您看可以嘛?

发表评论

电子邮件地址不会被公开。必填项已用 * 标注