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

Question

我有一个包含正整数的数组。此数组中除一个元素外的所有元素都没有重复项。查找唯一元素的方法是使用 XOR 按位运算符，其中 returns 仅当其中一个元素为 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

XOR输入n个数就好比统计每个位置有多少个1，如果是奇数就把对应的输出位设置为1。您 XOR 使用它们的顺序无关紧要。

如果一个数组包含 x 对相等的数字和一个唯一的数字，相等对的位相互抵消（因为它们在每个位置贡献偶数个 1），只剩下唯一编号。

例如，取下面的数字列表：

100100101
010110110
101101100 // the unique number
100100101
010110110

统计每个位置1的个数：

321521522

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

101101100

这是列表中的唯一编号。

Answer 2

像数学一样看待它，而不是代码；并使用 ^ 表示 bit-level xor，我们可以说

xor 可交换：A ^ B = B ^ A
异或结合：(A ^ B) ^ C = A ^ (B ^ C)
与零异或不执行任何操作：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

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

Bitwise XOR operator to find missing unique ID

java

bitwise-operators