GCD maximum common divisor

gcd function

10 Advance preparation gcd

Let's start with a simple gcd function （ Recursive ）, It should be understood at a glance , I won't talk about it here .

int gcd(int a,int b){
    
    return a%b==0?b:gcd(b,a%b);
}

Here is the optimization , It is similar to the above principle , But the complexity is a little lower .

int gcd( int a , int b )
{
    
	return b == 0 ? a : gcd( b , a%b ) ;	
}

Binary fetch gcd
Learned from big brother Wang Yu , If even Wang Yu doesn't know , Then you have learned in vain QAQ

First, introduce a concept ,“^” Symbol , It's a decimal number , Or by bit .
Take a chestnut ;
5 Binary for 00101
9 Binary for 01001
After XOR, it is 01100
by 12
The following is the binary exchange of two numbers , It belongs to fast forward and fast read , Because binary is faster than decimal .

void swap( int &a , int &b ) 
{
    
    a=a^b;
    b=a^b;
    a=a^b;
}

And then use this to do the operation gcd function

int gcd(int a,int b){
    
	while(b=^a=^b^=a%=b);
	return a;
// First a and b The remainder of , And then use the binary exchange rule 
	// The algorithm is the same as the previous decimal system 
	// return a Because a%b==0 however a and b Exchanged , So back a Value of equals before return b Value 
}