生成异或为 N 的所有数字对

Question

我需要找到生成所有对 (A,B) 的方法，使得 A<=10^5、B<=10^5、N<=10^5 和 A XOR B == N . N 作为输入给出。

我知道平方时间的解决方案，检查两个 for 中的所有值，但我认为有更快的解决方案。

提前致谢。

Answer 1

以下应该有效：

for A = 0 to 65536 do /* 65536 > 10^5 / 2 */
    B = A xor N
    if A <= 100000 and B <= 100000
        print A, B
        print B, A

Generating all pairs of numbers which XOR is N