누락 된 고유 ID를 찾기위한 비트 XOR 연산자

Question

나는 양의 정수를 가진 배열을 가지고 있습니다. 이 배열에있는 하나의 요소를 제외한 모든 요소에는 복제본이 없습니다. 고유 한 요소를 찾는 방법은 요소 중 하나가 1 인 경우에만 1을 반환하는 XOR 비트 연산자를 사용하는 것입니다.

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 (34)과 XOR 연산되어 0에서 시작 UNIQUEID와 XOR 연산되고 그 결과는 다음 XOR이다

다음

는 코드 배열 40의 다음 정수로 처리하면 전체 배열을 통과합니다.

심지어는 중단 점을 설정하고 전체 플로우를 한 번에 한 줄씩 처리 한 후에도 uniqueId (값 0부터 시작 함)를 사용한 XORing이 배열에서 중복되지 않는 정수를 찾는 데 도움이 될 수 있습니다. ?

40과 같이 XOR되어 (값이 0이되어야 함) 중복되어 있는지 확인해야합니다. 여기서 우리는 배열에서 첫 번째 정수와 0을 XOR하고 배열에서 후속 숫자로 결과를 얻습니다. 무엇이 누락 되었습니까?/

Answer 1

XOR n 개의 숫자는 각 위치의 1 비트 수를 세는 것과 같고, 카운트가 홀수 일 경우 해당 출력 비트를 1로 설정하는 것과 같습니다. XOR의 순서는 중요하지 않습니다.

배열에 x 쌍의 같은 수와 하나의 고유 번호가 포함되어있는 경우 등호 쌍의 비트는 서로를 취소합니다 (각 위치에서 1의 짝수 수를 제공하기 때문에). 번호.

100100101 
010110110 
101101100 // the unique number 
100100101 
010110110 

각 위치에 1의 개수 개수 : XOR의

321521522 

결과 (각각 홀수 카운트에 1 비트)

예를 들면, 번호의 다음 목록을 취

101101100 

이는 목록의 단일 고유 번호입니다.

Answer 2

코드가 아니라 수학과 비슷하게 보입니다. 및 bit-level xor을 의미하는 ^를 사용하여, 우리는

• XOR은 교환 법칙이 성립이라고 말할 수 있습니다 : A^B = B^A
• XOR은 결합이다 : (A^B)^C = A^(B^C) 0으로 XOR 연산
• 아무것도하지 : 두 번 뭔가를 XOR 연산 A^0 = A
• 그것을 삭제합니다 : A^A = 0

첫 번째 두 속성은 x0 시퀀스의 임의의 순서 변경 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