按位异或运算符用于查找缺失的唯一ID

Question

我有一个由正整数组成的数组。除了其中一个元素外，这个数组中的所有元素都没有重复。找到唯一的元素的方法是使用XOR位运算符，它只在其中一个元素为1时返回1，否则返回false。

以下是代码：

public class Bitter {

    public static void main(String[] args) {
        int[] deliveryIds = {34, 40, 2, 21, 50, 40, 34, 2, 50};
        System.out.println(new Bitter().findUniqueDeliveryId(deliveryIds));
    }

    public int findUniqueDeliveryId(int[] deliveryIds) {
        int uniqueDeliveryId = 0;

        for(int i = 0; i < deliveryIds.length; i++) {
            uniqueDeliveryId ^= deliveryIds[i];
        }

        return uniqueDeliveryId;
    }

}

在循环中，数组中的每个整数都会与uniqueId进行异或运算，uniqueId从0开始。然后，0与34进行XOR运算。然后将结果与数组中的下一个整数40进行XOR运算，并遍历整个数组。

即使设置断点并逐行查看整个流程，我仍然无法理解如何通过与uniqueId（从值0开始）进行XOR运算来帮助我们找到数组中的非重复整数？

如果像这里一样将数字40与自身进行XOR运算（得到值0），以确认它是重复的，那么不应该吗？在这里，我们将0与数组中的第一个整数进行XOR运算，然后将结果与数组中的下一个数字进行XOR运算。我错过了什么吗？

- Pha3drus

---

我认为你的意思是“这个数组中除了一个元素外，其他所有元素都有重复项。” - Klitos Kyriacou

Answer 1

XOR n 个数字就像数出每个位置中 1 的位数，如果计数是奇数，则将相应的输出位设置为 1。你 XOR 它们的顺序无关紧要。

如果一个数组包含 x 对相等的数字和一个唯一的数字，则相等对的位会相互抵消掉(因为它们在每个位置上贡献了偶数个 1)，留下的只是那个唯一数字的位。

例如，取以下数字列表：

100100101
010110110
101101100 // the unique number
100100101
010110110

统计每个位置上1的数量：

321521522

XOR结果（每个奇数计数器中的1位）：

101101100 

这是列表中唯一的一个数字。

- Eran

---

太好的讲解了！！！终于让我理解为什么这样可行哈哈哈 - SamuelP

Answer 2

如果我们把它看作数学问题，而不是代码问题；并使用^表示按位异或，那么我们可以说：

• xor具有交换律：A ^ B = B ^ A
• xor具有结合律：(A ^ B) ^ C = A ^ (B ^ C)
• xor对0进行异或操作等于不变：A ^ 0 = A
• 两次异或同一个数等于将其删除：A ^ A = 0

前两个性质意味着，无论如何重新排列异或序列，都将产生完全相同的结果。

因此，给定包含重复值的序列，通过异或运算将删除所有重复项：

   A ^ B ^ X ^ A ^ B  =  A^A ^ B^B ^ X  =  0 ^ 0 ^ X   =  X
                      \ reorder         \ xoring twice \ removing zeroes

注意，这个技巧只适用于只有一个元素不重复的情况。如果有多个非均匀重复的元素，则结果将是所有非均匀重复元素的异或：

   A ^ B ^ C ^ A  =  A^A ^ B ^ C  =  B ^ C

- tucuxi

---

我认为XOR的另一个重要属性是可结合性，这一点很重要，因为它可以帮助我们理解为什么它有效：(A ^ B) ^ C = A ^ (B ^ C)。 - Klitos Kyriacou

真的，编辑以反映。我认为一个暗示另一个，但是能够找到反例：a＃b =（a + b）/ 2是可交换的，但不是可结合的。如果没有这两个属性，您就无法自由地重新排序。因此感谢评论-改进了答案，并学习了一些数学。 - tucuxi