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

本文主要是介绍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

这篇关于C#，最大公约数（GCD）斯坦因（Stein）算法的源代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---