<?php
/**
 * 问题：求两个自然数的最大公约数。
 *
 * 分析：这个是基础的数学问题，最大公约数指两个数字公共的约数中最大的，例如数字6的约数有1、2、3、6，数字9的约数有1、3、9，则数字6和数字9的公共约数有1和3，其中3是最大的公约数。
 *
 * 第五种思路：结合辗转相除法和更相减损法，在更相减损法的基础上使用移位运算
 *
 * 不但避免了取模运算，而且算法性能稳定，时间复杂度是a和b中较大数的二进制位数，即O(log(max(a, b)))
 */

$a = 50;
$b = 88;
$c = gcd($a, $b);
var_dump($c);

/**
 * 递归计算最大的公约数
 * @param int $a
 * @param int $b
 * @return mixed
 */
function gcd($a, $b)
{
    if (!is_numeric($a) || !is_numeric($b)) {
        return false;
    }

    if ($a == $b) {
        return $a;
    }

    //保证参数$a永远大于等于参数$b，为减少代码量
    if ($a < $b) {
        return gcd($b, $a);
    } else {
        //和1做按位与运算，判断奇偶
        if (is_even($a) && is_even($b)) {
            return (gcd($a >> 1, $b >> 1) << 1);
        } elseif (is_even($a) && !is_even($b)) {
            return gcd($a >> 1, $b);
        } elseif (!is_even($a) && is_even($b)) {
            return gcd($a, $b >> 1);
        } else {
            return gcd($b, $a - $b);
        }
    }
}

/**
 * 判断奇偶数，减少迭代次数,奇数为false,偶数为true
 * @param int $a
 * @return bool
 */
function is_even($a)
{
    return !($a & 1);
}