斯坦算法 或 二进制GCD算法 是计算两个非负整数的最大公约数的算法。斯坦的算法用算术移位、比较和减法代替除法。
null
例如：
Input: a = 17, b = 34 Output : 17Input: a = 50, b = 49Output: 1
使用Stein算法GCD（a，b）查找GCD的算法
- 如果a和b都为0，则gcd为零gcd（0，0）=0。
- gcd（a，0）=a和gcd（0，b）=b，因为一切都除以0。
- 如果a和b都是偶数，则gcd（a，b）=2*gcd（a/2，b/2），因为2是公约数。2的乘法可以用位移位运算符完成。
- 如果a是偶数，b是奇数，则gcd（a，b）=gcd（a/2，b）。同样，如果a是奇数，b是偶数，那么 gcd（a，b）=gcd（a，b/2）。这是因为2不是公约数。
- 如果a和b都是奇数，那么gcd（a，b）=gcd（|a-b |/2，b）。请注意，两个奇数之差是偶数
- 重复步骤3-5，直到a=b，或直到a=0。在任何一种情况下，GCD都是幂（2，k）*b，其中幂（2，k）是2，提升到k的幂，k是在步骤2中找到的2的公因数的数量。
迭代实现
C++
// Iterative C++ program to // implement Stein's Algorithm #include <bits/stdc++.h> using namespace std; // Function to implement // Stein's Algorithm int gcd( int a, int b) { /* GCD(0, b) == b; GCD(a, 0) == a, GCD(0, 0) == 0 */ if (a == 0) return b; if (b == 0) return a; /*Finding K, where K is the greatest power of 2 that divides both a and b. */ int k; for (k = 0; ((a | b) & 1) == 0; ++k) { a >>= 1; b >>= 1; } /* Dividing a by 2 until a becomes odd */ while ((a & 1) == 0) a >>= 1; /* From here on, 'a' is always odd. */ do { /* If b is even, remove all factor of 2 in b */ while ((b & 1) == 0) b >>= 1; /* Now a and b are both odd. Swap if necessary so a <= b, then set b = b - a (which is even).*/ if (a > b) swap(a, b); // Swap u and v. b = (b - a); } while (b != 0); /* restore common factors of 2 */ return a << k; } // Driver code int main() { int a = 34, b = 17; printf ( "Gcd of given numbers is %d" , gcd(a, b)); return 0; } |
JAVA
// Iterative Java program to // implement Stein's Algorithm import java.io.*; class GFG { // Function to implement Stein's // Algorithm static int gcd( int a, int b) { // GCD(0, b) == b; GCD(a, 0) == a, // GCD(0, 0) == 0 if (a == 0 ) return b; if (b == 0 ) return a; // Finding K, where K is the greatest // power of 2 that divides both a and b int k; for (k = 0 ; ((a | b) & 1 ) == 0 ; ++k) { a >>= 1 ; b >>= 1 ; } // Dividing a by 2 until a becomes odd while ((a & 1 ) == 0 ) a >>= 1 ; // From here on, 'a' is always odd. do { // If b is even, remove // all factor of 2 in b while ((b & 1 ) == 0 ) b >>= 1 ; // Now a and b are both odd. Swap // if necessary so a <= b, then set // b = b - a (which is even) if (a > b) { // Swap u and v. int temp = a; a = b; b = temp; } b = (b - a); } while (b != 0 ); // restore common factors of 2 return a << k; } // Driver code public static void main(String args[]) { int a = 34 , b = 17 ; System.out.println( "Gcd of given " + "numbers is " + gcd(a, b)); } } // This code is contributed by Nikita Tiwari |
Python3
# Iterative Python 3 program to # implement Stein's Algorithm # Function to implement # Stein's Algorithm def gcd(a, b): # GCD(0, b) == b; GCD(a, 0) == a, # GCD(0, 0) == 0 if (a = = 0 ): return b if (b = = 0 ): return a # Finding K, where K is the # greatest power of 2 that # divides both a and b. k = 0 while (((a | b) & 1 ) = = 0 ): a = a >> 1 b = b >> 1 k = k + 1 # Dividing a by 2 until a becomes odd while ((a & 1 ) = = 0 ): a = a >> 1 # From here on, 'a' is always odd. while (b ! = 0 ): # If b is even, remove all # factor of 2 in b while ((b & 1 ) = = 0 ): b = b >> 1 # Now a and b are both odd. Swap if # necessary so a <= b, then set # b = b - a (which is even). if (a > b): # Swap u and v. temp = a a = b b = temp b = (b - a) # restore common factors of 2 return (a << k) # Driver code a = 34 b = 17 print ( "Gcd of given numbers is " , gcd(a, b)) # This code is contributed by Nikita Tiwari. |
C#
// Iterative C# program to implement // Stein's Algorithm using System; class GFG { // Function to implement Stein's // Algorithm static int gcd( int a, int b) { // GCD(0, b) == b; GCD(a, 0) == a, // GCD(0, 0) == 0 if (a == 0) return b; if (b == 0) return a; // Finding K, where K is the greatest // power of 2 that divides both a and b int k; for (k = 0; ((a | b) & 1) == 0; ++k) { a >>= 1; b >>= 1; } // Dividing a by 2 until a becomes odd while ((a & 1) == 0) a >>= 1; // From here on, 'a' is always odd do { // If b is even, remove // all factor of 2 in b while ((b & 1) == 0) b >>= 1; /* Now a and b are both odd. Swap if necessary so a <= b, then set b = b - a (which is even).*/ if (a > b) { // Swap u and v. int temp = a; a = b; b = temp; } b = (b - a); } while (b != 0); /* restore common factors of 2 */ return a << k; } // Driver code public static void Main() { int a = 34, b = 17; Console.Write( "Gcd of given " + "numbers is " + gcd(a, b)); } } // This code is contributed by nitin mittal |
PHP
<?php // Iterative php program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd( $a , $b ) { // GCD(0, b) == b; GCD(a, 0) == a, // GCD(0, 0) == 0 if ( $a == 0) return $b ; if ( $b == 0) return $a ; // Finding K, where K is the greatest // power of 2 that divides both a and b. $k ; for ( $k = 0; (( $a | $b ) & 1) == 0; ++ $k ) { $a >>= 1; $b >>= 1; } // Dividing a by 2 until a becomes odd while (( $a & 1) == 0) $a >>= 1; // From here on, 'a' is always odd. do { // If b is even, remove // all factor of 2 in b while (( $b & 1) == 0) $b >>= 1; // Now a and b are both odd. Swap // if necessary so a <= b, then set // b = b - a (which is even) if ( $a > $b ) swap( $a , $b ); // Swap u and v. $b = ( $b - $a ); } while ( $b != 0); // restore common factors of 2 return $a << $k ; } // Driver code $a = 34; $b = 17; echo "Gcd of given numbers is " . gcd( $a , $b ); // This code is contributed by ajit ?> |
Javascript
<script> // Iterative JavaScript program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd( a, b) { /* GCD(0, b) == b; GCD(a, 0) == a, GCD(0, 0) == 0 */ if (a == 0) return b; if (b == 0) return a; /*Finding K, where K is the greatest power of 2 that divides both a and b. */ let k; for (k = 0; ((a | b) & 1) == 0; ++k) { a >>= 1; b >>= 1; } /* Dividing a by 2 until a becomes odd */ while ((a & 1) == 0) a >>= 1; /* From here on, 'a' is always odd. */ do { /* If b is even, remove all factor of 2 in b */ while ((b & 1) == 0) b >>= 1; /* Now a and b are both odd. Swap if necessary so a <= b, then set b = b - a (which is even).*/ if (a > b){ let t = a; a = b; b = t; } b = (b - a); } while (b != 0); /* restore common factors of 2 */ return a << k; } // Driver code let a = 34, b = 17; document.write( "Gcd of given numbers is " + gcd(a, b)); // This code contributed by gauravrajput1 </script> |
输出
Gcd of given numbers is 17
递归实现
C++
// Recursive C++ program to // implement Stein's Algorithm #include <bits/stdc++.h> using namespace std; // Function to implement // Stein's Algorithm int gcd( int a, int b) { if (a == b) return a; // GCD(0, b) == b; GCD(a, 0) == a, // GCD(0, 0) == 0 if (a == 0) return b; if (b == 0) return a; // look for factors of 2 if (~a & 1) // a is even { if (b & 1) // b is odd return gcd(a >> 1, b); else // both a and b are even return gcd(a >> 1, b >> 1) << 1; } if (~b & 1) // a is odd, b is even return gcd(a, b >> 1); // reduce larger number if (a > b) return gcd((a - b) >> 1, b); return gcd((b - a) >> 1, a); } // Driver code int main() { int a = 34, b = 17; printf ( "Gcd of given numbers is %d" , gcd(a, b)); return 0; } |
JAVA
// Recursive Java program to // implement Stein's Algorithm import java.io.*; class GFG { // Function to implement // Stein's Algorithm static int gcd( int a, int b) { if (a == b) return a; // GCD(0, b) == b; GCD(a, 0) == a, // GCD(0, 0) == 0 if (a == 0 ) return b; if (b == 0 ) return a; // look for factors of 2 if ((~a & 1 ) == 1 ) // a is even { if ((b & 1 ) == 1 ) // b is odd return gcd(a >> 1 , b); else // both a and b are even return gcd(a >> 1 , b >> 1 ) << 1 ; } // a is odd, b is even if ((~b & 1 ) == 1 ) return gcd(a, b >> 1 ); // reduce larger number if (a > b) return gcd((a - b) >> 1 , b); return gcd((b - a) >> 1 , a); } // Driver code public static void main(String args[]) { int a = 34 , b = 17 ; System.out.println( "Gcd of given" + "numbers is " + gcd(a, b)); } } // This code is contributed by Nikita Tiwari |
Python3
# Recursive Python 3 program to # implement Stein's Algorithm # Function to implement # Stein's Algorithm def gcd(a, b): if (a = = b): return a # GCD(0, b) == b; GCD(a, 0) == a, # GCD(0, 0) == 0 if (a = = 0 ): return b if (b = = 0 ): return a # look for factors of 2 # a is even if ((~a & 1 ) = = 1 ): # b is odd if ((b & 1 ) = = 1 ): return gcd(a >> 1 , b) else : # both a and b are even return (gcd(a >> 1 , b >> 1 ) << 1 ) # a is odd, b is even if ((~b & 1 ) = = 1 ): return gcd(a, b >> 1 ) # reduce larger number if (a > b): return gcd((a - b) >> 1 , b) return gcd((b - a) >> 1 , a) # Driver code a, b = 34 , 17 print ( "Gcd of given numbers is " , gcd(a, b)) # This code is contributed # by Nikita Tiwari. |
C#
// Recursive C# program to // implement Stein's Algorithm using System; class GFG { // Function to implement // Stein's Algorithm static int gcd( int a, int b) { if (a == b) return a; // GCD(0, b) == b; // GCD(a, 0) == a, // GCD(0, 0) == 0 if (a == 0) return b; if (b == 0) return a; // look for factors of 2 // a is even if ((~a & 1) == 1) { // b is odd if ((b & 1) == 1) return gcd(a >> 1, b); else // both a and b are even return gcd(a >> 1, b >> 1) << 1; } // a is odd, b is even if ((~b & 1) == 1) return gcd(a, b >> 1); // reduce larger number if (a > b) return gcd((a - b) >> 1, b); return gcd((b - a) >> 1, a); } // Driver code public static void Main() { int a = 34, b = 17; Console.Write( "Gcd of given" + "numbers is " + gcd(a, b)); } } // This code is contributed by nitin mittal. |
PHP
<?php // Recursive PHP program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd( $a , $b ) { if ( $a == $b ) return $a ; /* GCD(0, b) == b; GCD(a, 0) == a, GCD(0, 0) == 0 */ if ( $a == 0) return $b ; if ( $b == 0) return $a ; // look for factors of 2 if (~ $a & 1) // a is even { if ( $b & 1) // b is odd return gcd( $a >> 1, $b ); else // both a and b are even return gcd( $a >> 1, $b >> 1) << 1; } if (~ $b & 1) // a is odd, b is even return gcd( $a , $b >> 1); // reduce larger number if ( $a > $b ) return gcd(( $a - $b ) >> 1, $b ); return gcd(( $b - $a ) >> 1, $a ); } // Driver code $a = 34; $b = 17; echo "Gcd of given numbers is: " , gcd( $a , $b ); // This code is contributed by aj_36 ?> |
Javascript
<script> // JavaScript program to // implement Stein's Algorithm // Function to implement // Stein's Algorithm function gcd(a, b) { if (a == b) return a; // GCD(0, b) == b; GCD(a, 0) == a, // GCD(0, 0) == 0 if (a == 0) return b; if (b == 0) return a; // look for factors of 2 if ((~a & 1) == 1) // a is even { if ((b & 1) == 1) // b is odd return gcd(a >> 1, b); else // both a and b are even return gcd(a >> 1, b >> 1) << 1; } // a is odd, b is even if ((~b & 1) == 1) return gcd(a, b >> 1); // reduce larger number if (a > b) return gcd((a - b) >> 1, b); return gcd((b - a) >> 1, a); } // Driver Code let a = 34, b = 17; document.write( "Gcd of given " + "numbers is " + gcd(a, b)); </script> |
输出
Gcd of given numbers is 17
时间复杂性 ：O（N*N），其中N是较大数字中的位数。 你可能还喜欢—— 基本欧几里德算法和扩展欧几里德算法 工具书类 :
- https://en.wikipedia.org/wiki/Binary_GCD_algorithm
- http://andreinc.net/2010/12/12/binary-gcd-steins-algorithm-in-c/
- http://www.cse.unt.edu/~tarau/teaching/PP/numbertheory/GCD/Binary%20GCD%20算法。pdf
本文由 拉胡尔·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
