C#，最大公约数（GCD）斯坦因（Stein）算法的源代码

Stein 算法或二进制 GCD 算法是计算两个非负整数的最大公约数的算法。
Stein 的算法用算术移位、比较和减法代替除法。

using System;
using System.Text;

namespace Legalsoft.Truffer.Algorithm
{
? ? public static class GCD
? ? {
? ? ? ? /// <summary>
? ? ? ? /// Function to implement Stein's Algorithm
? ? ? ? /// </summary>
? ? ? ? /// <param name="a"></param>
? ? ? ? /// <param name="b"></param>
? ? ? ? /// <returns></returns>
? ? ? ? public static int Stein_Algorithm(int a, int b)
? ? ? ? {
? ? ? ? ? ? if (a == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return b;
? ? ? ? ? ? }
? ? ? ? ? ? if (b == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return a;
? ? ? ? ? ? }

? ? ? ? ? ? int k;
? ? ? ? ? ? for (k = 0; ((a | b) & 1) == 0; ++k)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? a >>= 1;
? ? ? ? ? ? ? ? b >>= 1;
? ? ? ? ? ? }

? ? ? ? ? ? while ((a & 1) == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? a >>= 1;
? ? ? ? ? ? }
? ? ? ? ? ? do
? ? ? ? ? ? {
? ? ? ? ? ? ? ? while ((b & 1) == 0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? b >>= 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (a > b)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? int temp = a;
? ? ? ? ? ? ? ? ? ? a = b;
? ? ? ? ? ? ? ? ? ? b = temp;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? b = (b - a);
? ? ? ? ? ? } while (b != 0);

? ? ? ? ? ? return a << k;
? ? ? ? }
? ? }
}

----------------------------------------------------------------------

POWER BY TRUFFER.CN