1行のコードは最大公約数を求めます(ユークリッドアルゴリズム)
772 ワード
本稿では,通常のユークリッドアルゴリズム(転がり相除去法)ではなく,ビット操作を用いて実現したユークリッドアルゴリズムを紹介する.ビット操作を利用してユークリッドアルゴリズムを実現するには主に以下の2つの利点がある:1.コード量が少ない2.能率が高い.
まず、ユークリッドアルゴリズムが最大公約数を求める方法は、1.rをa/bにして得られた残数(0<=r
b^=a^=b^=a%=bは、以下の4つのa=a%bに分解することができる.b=b^a; a=a^b; b=b^a;
第1文はaで残数を残し,残りの3文はa,bを交換し,whileに合わせてこのときbが0であるか否かを判断し,0でない場合はループを継続する.また、a,bが大きいか小さいかの問題を心配する必要はなく、a
まず、ユークリッドアルゴリズムが最大公約数を求める方法は、1.rをa/bにして得られた残数(0<=r
int gcd(int a, int b){
while(b^=a^=b^=a%=b);
return a;
} b^=a^=b^=a%=bは、以下の4つのa=a%bに分解することができる.b=b^a; a=a^b; b=b^a;
第1文はaで残数を残し,残りの3文はa,bを交換し,whileに合わせてこのときbが0であるか否かを判断し,0でない場合はループを継続する.また、a,bが大きいか小さいかの問題を心配する必要はなく、a