비트 XOR (배타적 OR)은 무엇을 의미합니까?
C # 또는 일반적으로 이항 연산자, 특히 ^-독점 또는 .
예를 들면 :
양의 정수 배열이 주어집니다. 홀수 번 발생하는 하나의 숫자를 제외하고 모든 숫자는 짝수 번 발생합니다. O (n) 시간과 상수 공간에서 숫자를 찾으십시오.
^로 다음과 같이 수행 할 수 있습니다. 모든 요소의 비트 단위 XOR을 수행합니다. 마지막으로 우리는 홀수 발생 횟수를 얻습니다.
어떻게 작동합니까?
내가 할 때 :
int res = 2 ^ 3;
res = 1;
int res = 2 ^ 5;
res = 7;
int res = 2 ^ 10;
res = 8;
실제로 무슨 일이 일어나고 있습니까? 다른 비트 마법은 무엇입니까? 조회 할 수있는 참고 자료가 있습니까?
작동 방식을 확인 예상 비트 연산이 코드 비트에서 작동하기 때문에 먼저 두 피 연산 유효성을 확인해야합니다.
그런 다음 특정 연산자에 대한 진리표 를 적용 할 수 있습니다 . 두 피연산자 (동일한 자리 값)에서 동일한 위치를 각 비트에 대해 작동합니다. 따라서 가장 필요한 비트 (MSB)가 MSB A와 결합되어 B결과의 MSB가 생성됩니다.
예 : 2^10:
0010 2
XOR 1010 8 + 2
----
1 xor(0, 1)
0 xor(0, 0)
0 xor(1, 1)
0 xor(0, 0)
----
= 1000 8
결과는 8입니다.
나는 다소 오래된 게시물이라는 것을 알고 있다고 생각하는 것을 찾는 동안 우연히 발견하고 단순화하고 싶었습니다.
XOR (eXclusive OR / 또는 또는)은 토글 뒤에 / 간단히 변환 할 수 있습니다.
지정된 비트를 제외하거나 포함합니다.
4 비트 (1111)를 사용하여 0-15에서 16 개의 가능한 결과를 얻습니다.
decimal | binary | expanded
0 | 0000 |
1 | 0001 |
2 | 0010 |
3 | 0011 | (1+2)
4 | 0100 |
5 | 0101 | (1+4)
6 | 0110 | (2+4)
7 | 0111 | (1+2+4)
8 | 1000 |
9 | 1001 | (1+8)
10 | 1010 | (2+8)
11 | 1011 | (1+2+8)
12 | 1100 | (4+8)
13 | 1101 | (1+4+8)
14 | 1110 | (2+4+8)
15 | 1111 | (1+2+4+8)
이진 값의 왼쪽에있는 십진수 값은 XOR 및 기타 비트 연산에 사용되는 숫자 값입니다.
예 : 0011비트 1과 2는 on으로, 비트 4와 8은 off로 이어집니다. 3선택한 비트를 나타냅니다. 내기 위해 의 십진수 값으로 표시되고 확장 된 형식으로 1+2.
XOR이면의 논리에서 무슨 일이 일어나고 있는지에
대한 게시물의 몇 가지 예가 있습니다 .
2 ^ 3 = 1
- 2는 1 + 2 (3) 2 = 1 의 구성원입니다.
2 ^ 5 = 7
- 2는 1 + 4 의 구성원이 아닙니다. (5) 더하기 2 = 1 + 2 + 4 (7)
2 ^ 10 = 8
- 2는 2 + 8 (10) remove 2 = 8 의 구성원입니다.
추가 예
1 ^ 3 = 2
- 1은 1 + 2 의 구성원입니다 (3) remove 1 = 2
4 ^ 5 = 1
- 4는 1 + 4 (5) 4 = 1 의 구성원입니다.
4 ^ 4 = 0
- 4는 자신의 구성원입니다. 제거 4 = 0
1 ^ 2 ^ 3 = 0
논리 : ((1 ^ 2) ^ (1 + 2))
- (1 ^ 2) 1은 2 add 2 = 1 + 2 (3) 의 구성원이 아닙니다.
- (3 ^ 3) 1과 2는 1 + 2의 구성원입니다. (3) 1 + 2 제거 (3) = 0
1 ^ 1 ^ 0 ^ 1 = 1
논리 : (((1 ^ 1) ^ 0) ^ 1)
- (1 ^ 1) 1은 1 remove 1 = 0의 구성원입니다.
- (0 ^ 0) 0은 0의 구성원입니다. 제거 0 = 0
- (0 ^ 1) 0은 1 add 1 = 1의 구성원이 아닙니다.
1 ^ 8 ^ 4 = 13
논리 : ((1 ^ 8) ^ 4)
- (1 ^ 8) 1은 8의 구성원이 아닙니다. 1 = 1 + 8 (9)
- (9 ^ 4) 1과 8은 4의 구성원이 아님 add 1 + 8 = 1 + 4 + 8 (13)
4 ^ 13 ^ 10 = 3
논리 : ((4 ^ (1 + 4 + 8)) ^ (2 + 8))
- (4 ^ 13) 4는 1 + 4 + 8 의 구성원입니다. (13) 제거 4 = 1 + 8 (9)
- (9 ^ 10) 8은 2 + 8 의 구성원입니다. (10) 8 = 2 제거
- 1은 2 의 구성원이 아님
+8(10) add 1 = 1 + 2 (3)4 ^ 10 ^ 13 = 3
논리 : ((4 ^ (2 + 8)) ^ (1 + 4 + 8))
- (4 ^ 10) 4는 2 + 8 의 구성원이 아닙니다. (10) 더하기 4 = 2 + 4 + 8 (14)
- (14 ^ 13) 4와 8은 1 + 4 + 8의 구성원입니다. (13) 4 + 8 = 1 제거
- 2는 1
+ 4 + 8(13) add 2 = 1 + 2 (3) 의 구성원이 아닙니다.
이것을 사용하는 방법은 XOR의 대수를 사용하는 것입니다. 인신 비트에 대해 알 필요가 없습니다.
x, y, z의 모든 숫자 :
XOR은 교환 적입니다. x ^ y == y ^ x
XOR은 연관성이 있습니다. x ^ (y ^ z) == (x ^ y) ^ z
ID는 0입니다. x ^ 0 == x
모든 요소는 고유 한 역입니다. x ^ x == 0
감안할 때, 접수 결과를 증명하는 것입니다. 시퀀스를 고려하십시오.
a ^ b ^ c ^ d ...
XOR은 교환 연관되지 않습니다. 따라서 요소를 정렬하십시오.
이제 동일한 동일한 요소 x ^ x를 0(자기 역 속성) 바꿀 수 있습니다 . 그리고 무엇이든 0제거 할 수 있습니다 (ID이기 때문에).
가능한 한 오래 반복하십시오. 짝수 번 나타나는 숫자는 정수 쌍을 가지므로 모두 0이되고 사라집니다.
결국에는 홀수 번 나타나는 하나의 요소 만 남게됩니다. 두 번 나타날 때마다 그 두 가지는 사라집니다. 결국 한 번만 남게됩니다.
[최신 정보]
이 증명에는 작업에 대한 특정 가정 만 필요합니다. 특히, 연산자 .가 있는 집합 S 에 다음 속성이 있다고 가정 합니다.
Assocativity : x . (y . z) = (x . y) . z어떤을 위해 x, y그리고 zS.에서
정체성 : S 에있는 모든 사람 e을 e . x = x . e = x위한 단일 요소가 있습니다 x.
폐쇄 : 모든 x및 yS에 x . y대해서도 S 에 있습니다.
자기 반전 : xS의 모든 경우x . x = e
밝혀진 바와 같이, 우리는 교환 성을 가정 할 필요가 없습니다. 우리는 그것을 증명할 수 있습니다 :
(x . y) . (x . y) = e (by self-inverse)
x . (y . x) . y = e (by associativity)
x . x . (y . x) . y . y = x . e . y (multiply both sides by x on the left and y on the right)
y . x = x . y (because x . x = y . y = e and the e's go away)
이제 저는 "개별 비트에 대해 알 필요가 없습니다"라고 말했습니다. 나는 이러한 속성을 만족하는 그룹이면 충분할 것이며 그러한 그룹이 반드시 XOR의 정수와 동형 일 필요는 없다고 생각했습니다.
그러나 @Steve Jessup은 댓글에서 내가 틀렸다는 것을 증명했습니다. 스칼라 곱셈을 {0,1}로 정의하는 경우 :
0 * x = 0
1 * x = x
... 그러면이 구조 는 정수 mod 2 에 대한 벡터 공간의 모든 공리를 충족합니다 .
따라서 이러한 구조는 구성 요소 별 XOR 아래의 비트 벡터 세트와 동형입니다.
비트 연산자는 정수 값 내의 비트를 작은 비트 배열 로 취급합니다 . 각각의 비트는 작은 bool값 과 같습니다 . 비트 배타적 또는 연산자를 사용할 때 연산자가 수행하는 작업에 대한 한 가지 해석은 다음과 같습니다.
- 첫 번째 값의 각 비트에 대해 두 번째 값의 해당 비트가 설정된 경우 비트를 토글합니다.
순 효과는 단일 비트가 시작되고 false총 "토글"수가 짝수이면 여전히 false끝에 있다는 것입니다. "토글"의 총 수가 홀수이면 true끝이됩니다.
"부울 값의 작은 배열"을 생각하면 이해하기 시작할 것입니다.
이것은 그 자체로 숫자의 XOR이 0이라는 단순한 사실에 기초합니다.
0 인 숫자의 XOR은 숫자 자체를 생성합니다.
따라서 배열이 있다면 = {5,8,12,5,12}입니다.
5는 2 번 발생합니다. 8 번이 1 번 발생합니다. 12 번이 2 번 발생합니다.
우리는 홀수 번 발생하는 숫자를 찾아야합니다. 분명히 8은 숫자입니다.
배열의 모든 요소에 대해 res = 0 및 XOR로 시작합니다.
int res=0; for(int i:array) res = res ^ i;
1st Iteration: res = 0^5 = 5
2nd Iteration: res = 5^8
3rd Iteration: res = 5^8^12
4th Iteration: res = 5^8^12^5 = 0^8^12 = 8^12
5th Iteration: res = 8^12^12 = 8^0 = 8
비트에 대한 XOR (배타적 OR) 연산자의 정의는 다음과 같습니다.
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
이를 상상하는 방법 중 하나는 오른쪽의 "1"이 왼쪽에서 비트를 변경하고 오른쪽의 0이 왼쪽의 비트를 변경하지 않는다고 말하는 것입니다. 그러나 XOR은 교환 적이므로 변이 반전 되어도 마찬가지입니다. 임의의 숫자가 이진 형식으로 표현 될 수 있으므로 두 숫자를 함께 XOR 할 수 있습니다.
그것이 교환 적이라는 것을 증명하기 위해, 당신은 그 정의를 살펴보고 양쪽의 모든 비트 조합에 대해 변이 변경되면 결과가 동일하다는 것을 알 수 있습니다. 연관성이 있음을 증명하기 위해 3 비트가 서로 XOR되는 모든 가능한 조합을 간단히 실행할 수 있으며 순서가 무엇이든 결과는 동일하게 유지됩니다.
이제 위를 증명했듯이 동일한 숫자를 XOR하면 어떻게되는지 살펴 보겠습니다. 작업은 개별 비트에서 작동하므로 0과 1의 두 숫자로만 테스트 할 수 있습니다.
0 XOR 0 = 0
1 XOR 1 = 0
따라서 숫자를 XOR하면 항상 0을 얻습니다 (믿거 나 말거나 XOR의 속성은 0이 CPU 레지스터에로드되어야 할 때 컴파일러에서 사용되었습니다. 비트 연산을 수행하는 것이 더 빠릅니다.) 레지스터에 0을 명시 적으로 푸시하는 것보다 컴파일러는 레지스터를 자체적으로 XOR하는 어셈블리 코드를 생성합니다.
이제 X XOR X가 0이고 XOR이 연관성이고 다른 모든 숫자가 두 번 (또는 다른 홀수 번) 반복 된 일련의 숫자에서 어떤 숫자가 반복되지 않았는지 알아 내야합니다. 반복되는 숫자가 함께 있으면 0으로 XOR됩니다. 0으로 XOR 처리 된 모든 항목은 그대로 유지됩니다. 따라서 이러한 시퀀스를 XOR-ing하면 반복되지 않는 (또는 짝수 번 반복되는) 숫자가 남게됩니다.
여기 에는 비트 조작으로 수행되는 다양한 기능의 샘플이 많이 있습니다. 일부는 매우 복잡 할 수 있으므로주의하십시오.
비트 연산을 이해하기 위해해야 할 일은 최소한 다음과 같습니다.
- 이진 형식의 입력 데이터
- 입력을 "혼합"하여 결과를 형성하는 방법을 알려주는 진리표
XOR의 경우 진리표는 간단합니다.
1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0
n결과에서 비트를 얻으려면 n첫 번째 및 두 번째 입력의 비트 에 규칙을 적용합니다 .
계산 1^1^0^1이나 다른 조합 을 시도 하면 홀수 1이 있으면 결과가 1이고 그렇지 않으면 0이라는 것을 알 수 있습니다. 또한 XOR 된 모든 숫자가 0이고 계산을 수행하는 순서가 중요하지 않습니다 1^1^(0^1) = 1^(1^0)^1. 예를 들어 .
즉, 목록의 모든 숫자를 XOR 할 때 중복 된 (또는 짝수 번 표시되는) 숫자가 0으로 XOR되고 홀수 번 표시되는 숫자 만 남게됩니다.
참조 URL : https://stackoverflow.com/questions/6398427/what-does-bitwise-xor-exclusive-or-mean
'ProgramingTip' 카테고리의 다른 글
| Cordova + Angularjs + 장치 준비 (0) | 2020.12.31 |
|---|---|
| Android에서 알림의 가운데 텍스트 (0) | 2020.12.31 |
| PHP를 사용하여 디렉토리의 모든 폴더 하위 폴더 및 파일 프로그램 (0) | 2020.12.31 |
| 자바 스크립트 : 배열로 주어진 객체 이름을 사용하여 중첩 된 객체를 동적으로 만드는 방법 (0) | 2020.12.31 |
| 쿠키 PHP의 배열 (0) | 2020.12.31 |