java - 计算 2 个相关方程的解数

Question

如何找到解决方案的数量

s = a+b
x = a^b

当给定s和x时，^表示xor?

那么对于 (0,0) 或 (31,31) 或 (15,10) 呢？

我试过将 x 转换成二进制字符串，但之后我不确定该把它放在哪里。

Answer 1

如果没有解决方案，方法 solution 返回 null。如果有解决方案，它返回 a(仅针对一个解决方案)。您可以通过执行 s - a 或 x ^ a 来获得 b。

如果存在解决方案，则解决方案的总数(long)是 2 的 Long.bitCount(x) 次方。

例如，s = 24, x = 6 的解是 a = 9, b = 15。二进制:

 9 = 1001
15 = 1111

这些数字在 2 个位置不同，因此总共有 Math.pow(2, 2) = 4 解。对于部分或所有这些位置，您可以通过将 a 的位与 b 的相应位交换来获得所有可能的解决方案。

这给出了 3 个进一步的解决方案。

11 = 1011     13 = 1101     15 = 1111
13 = 1101     11 = 1011      9 = 1001

代码如下:

public static Long solution(long s, long x) {
    return recursive(s, x, false);
}

private static Long recursive(long s, long x, boolean carry) {
    boolean s1 = (s & 1) == 1;
    boolean x1 = (x & 1) == 1;
    if ((s1 == x1) == carry)
        return null;
    if ((s == 0 || s == -1) && (x == 0 || x == -1))
        return s;
    Long a;
    if (x1)
        return (a = recursive(s >> 1, x >> 1, carry)) == null ? null : a << 1;
    if ((a = recursive(s >> 1, x >> 1, false)) != null)
        return a << 1;
    if ((a = recursive(s >> 1, x >> 1, true)) != null)
        return 1 + (a << 1);
    return null;
}

我决定不编写返回所有解决方案的 HashSet 的方法，因为这些集合在某些情况下会非常庞大​​。但是，您可以编写一种方法来生成所有可能的解决方案，而无需将它们全部存储在内存中。参见，例如，Generating all binary numbers based on the pattern