计算2个相关方程的解的数量

Question

我如何找到解决方案的数量

s = a+b
x = a^b

当s和x中,将其^手段xor？

因此,对于像(0,0)或(31,31)或(15,10)？

我已经尝试过转换x成二进制字符串,但之后我不知道该去哪里.

Answer 1

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

如果存在解，则解的总数（在 中long）为 2 的 次方Long.bitCount(x)。

例如，找到s = 24, 的解x = 6为a = 9, b = 15。以二进制表示：

 9 = 1001
15 = 1111

Math.pow(2, 2) = 4这些数字有 2 个位置不同，因此总共有解决方案。通过将 的位与部分或全部位置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所有解决方案，因为在某些情况下，这些集合会很大。但是，您可以编写一个方法来生成所有可能的解决方案，而无需将它们一次全部存储在内存中。例如，请参阅根据模式生成所有二进制数