java - 用于查找丢失的唯一 ID 的按位 XOR 运算符

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;
    }

}

在循环中，数组中的每个整数都与从 0 开始的 uniqueId 进行异或运算。然后，0 与 34 进行异或运算。然后将结果与数组 40 中的下一个整数进行异或运算，然后我们开始通过整个阵列。

即使在设置断点并一次一行地完成整个流程后，我仍然无法理解，与 uniqueId(从值 0 开始)进行异或如何帮助我们找到数组中的非重复整数？

不应该像 40 这样的数字与自身进行异或运算(结果为 0)，以确认它是重复的。与这里不同的是，我们将 0 与数组中的第一个整数进行异或运算，结果与数组中的后续数字进行异或运算。我错过了什么/

Answer 1

XORn 个数字就像计算每个位置的 1 位的个数，如果计数为奇数，则将相应的输出位设置为 1。您对它们进行 XOR 处理的顺序无关紧要。

如果一个数组包含 x 对相等数字和一个唯一数字，则相等对的位相互抵消(因为它们在每个位置贡献偶数个 1)，只剩下唯一数字的位.

例如，采用以下数字列表:

100100101
010110110
101101100 // the unique number
100100101
010110110

统计每个位置1的个数:

321521522

XOR 的结果(每个奇数计数 1 位):

101101100 

这是列表中的唯一编号。