关于Binary GCD
  • 板块学术版
  • 楼主lzqy_
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/5/26 21:55
  • 上次更新2023/10/28 00:34:17
查看原帖
关于Binary GCD
288716
lzqy_楼主2022/5/26 21:55

rt,为什么以下两个代码有极大的效率差距?

il int gcd(int a,int b){
	int ab=__builtin_ctz(a);
	int bb=__builtin_ctz(b);
	int tmp,c=min(ab,bb);
	b>>=bb;
	while(a){
		a>>=ab,tmp=a-b;
		b=min(a,b),a=abs(tmp);
		ab=__builtin_ctz(a); 
	}
	return b<<c;
}
il int gcd(int a,int b){
	int ab=__builtin_ctz(a);
	int bb=__builtin_ctz(b);
	int tmp,c=min(ab,bb);
	b>>=bb;
	while(a){
		a>>=ab,tmp=a-b;
		b=min(a,b),a=abs(tmp);
		ab=__builtin_ctz(tmp); 
	}
	return b<<c;
}

第一个代码效率远低于第二个代码。

2022/5/26 21:55
加载中...