java - 如何优化此算法以处理大整数？

Question

我有两个整数 x 和 y。

规则:

1. 如果 x > y : x = x - y 且 y = 2 * y;
2. 如果 y > x : y = y - x 且 x = 2 * x;
3. 如果 y == x :不是无限循环

问题是，这两个整数会不会是一个无限循环？

这是我的代码:

private static boolean IsPairLoop(int first, int second)
{
    boolean loop = false;
    HashMap<Integer, Integer> round_record = new HashMap<>();
    int[] first_round = new int[]{first, second};

    while ((first_round[0] != -1 && first_round[1] != -1))
    {
        if (round_record.containsKey(first_round[0]))
        {
            loop = true;
            break;
        }
        round_record.put(first_round[0], first_round[1]);
        PlayRound(first_round);
    }
    return loop;
}

private static void PlayRound(int[] round)
{
    if (round[0] > round[1])
    {

       round[0] -= round[1];
       round[1] += round[1];

    }
    else if (round[0] < round[1])
    {

       round[1] -= round[0];
       round[0] += round[0];

    }
    else
    {
        round[0]  = -1;
        round[1]  = -1;
    }
}

这适用于小整数。但是，当整数差异非常大时，这会非常慢。 x 和 y 的整数范围都是 1 到 2^30。即使整数差异很大，我该怎么做才能加快速度？

Answer 1

在这个问题中，和x + y是不变的，如果是奇数，x == y是不可能的。

那么如果 x 和 y 具有相同的奇偶性，在一次迭代后它们变为偶数并保持偶数，如果你将两者除以 2。

因此“瞬时”解决方案:

while (x + y) & 1 == 0:
    if x == y:
        print "Not infinite"
        break
    if x > y:
        x= (x - y) / 2
    else:
        y= (y - x) / 2
else:
    print "Infinite"

由于参数之一在每次迭代中至少丢失一位，因此 32 位整数的迭代永远不会超过 64 次(实际上更少，大多数时候为 0!)。

---

一个变体是可能的并且对大数字有意义:

• 如果 x == y，得出有限结论。

• 如果 x 和 y 有不同数量的尾随零，得出无穷大。

• 否则，丢弃尾随零并根据x > y 或y > x 执行归约并循环。