algorithm - 最大异或是最接近的数字

Question

如果我有一个L正整数列表并且给了我另一个数字K，我需要在列表中找到 XORK最大的数字。

我已经想到了一个算法。我想用反论点来验证它的正确性。我的算法是：

• 查找P=K 的补码（1 的补码）。现在在列表 L 中找到最接近 P 的数字。让这个数字为 N。K 和 N 的 XOR 将是最大的。
• I与给定数字集中的数字最接近的数字是与 I 的差最小的数字。

可以说，对于大于Plist的数字是不正确的L。但是数字不正确<=P吗？

请通过提供反驳论点/建议/想法告诉我我是否正确。

Answer 1

我认为你需要一个叫做 a 的东西Trie。

考虑从高到低的每一点K，当然我们可以贪婪地确定这个答案是否可以1，我的意思是，首先你尽力得到1024（甚至更高），然后512，然后256，然后。 .....终于到了最后一点1。

所以首先你需要检查列表L中的某个数字是否与最高位具有相反的值K，然后在所有选择的数字中，然后你需要找到与K第二高位具有相反值的数字。

现在解决方案很明显，构建一个Triewith L，从高到低确定答案的位，这对应于在那棵树上的旅行。

Answer 2

不，不对。

让K = 0011，这样P = 1100。让L = {0011, 1100}. 你的算法会选择N = 1100，这显然是不正确的，因为N^K = 0，而0011^N = 3。

Answer 3

编码和运行明显的蛮力算法所花费的时间远远少于您已经花费在此上的时间。