按位異或操作符找到丟失的唯一ID

我有一個具有正整數的數組。除此數組中的一個元素外，其他所有元素都沒有重複。找到唯一元素的方法是使用XOR位運算符，該運算符僅在其中一個元素爲1時返回1，否則返回false。按位異或操作符找到丟失的唯一ID

以下是代碼：

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異或從0開始。然後，0相異或34.其結果是然後XOR '用數組40中的下一個整數編輯，然後我們遍歷整個數組。

即使設置了斷點並一次檢查整行一行，我仍然無法理解，如何與uniqueId進行XOR（從值0開始）可以幫助我們在數組中找到非重複的整數？

不應該像40這樣的數字與自身異或（導致值爲0），以確認它是重複的。與此處不同的是，我們將數組中的第一個整數與0進行異或，並將結果與數組中的後續數進行異或運算。我錯過了什麼/

來源

2016-12-16 Pha3drus

我想你的意思是說「除了這個數組中的一個元素之外，所有元素都有重複。 –

XOR n個數字就像計算每個位置的1位數，如果計數是奇數，則將相應的輸出位設置爲1。你在哪裏的順序並不重要。

如果一個數組包含x個相等的數字和一個唯一的數字，那麼相等的數據對的位會相互抵消（因爲它們在每個位置貢獻偶數個1），只留下唯一的位數。

例如，以數字的下面的列表：

100100101 
010110110 
101101100 // the unique number 
100100101 
010110110

計數的1的中的每個位置的數目：

321521522

XOR結果（在每個奇數數1個比特）：

101101100

這是列表中的唯一唯一編號。

來源

2016-12-16 09:28:16 Eran

看着它像數學，而不是代碼;並使用^意味着bit-level xor，我們可以說，

XOR是可交換的：A^B = B^A
XOR是結合的：(A^B)^C = A^(B^C)
零異或什麼都不做：A^0 = A
異或東西兩次刪除它：A^A = 0

前兩個屬性意味着任何重新排序的序列xo rs會產生完全相同的結果。

因此，假定包含重複序列，它們都將通過XOR刪除：

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

來源

2016-12-16 09:39:14 tucuxi

我認爲XOR的另一個重要特性是爲了理解它爲什麼起作用，它是* associative *：（A^B）^ C = A ^（B^C）。 –

正確，編輯反映。我認爲這暗示了另一個，但能夠找到反例：a＃b =（a + b）/ 2是可交換的，但不是關聯的。沒有這兩個屬性，你不能自由地重新排序。所以感謝評論 - 改進的答案，並學會了一些數學。 – tucuxi

按位異或操作符找到丟失的唯一ID

回答

相關問題