2장 연산자/ 2절 비트 단위 연산자의 정의와 응용

우선, n비트 짜리 비트열(bit string) a에 대해 그 각각의 비트들을 a1, a2, ..., an이라 하자. 순서는 상관없으나, 일반적으로는 왼쪽부터 오른쪽으로 서수를 매긴 것으로 본다.

이제 임의의 비트 수가 같은 두 비트열 A, B에 대해,
AND OR XOR NOT 연산을 해보자.

A&B == (A1&B1)(A2&B2)...(An&Bn)
A|B == (A1|B1)(A2|B2)...(An&Bn)
A^B == (A1^B1) ... (An&Bn)
~A == (~A1)(~A2)...(~An)

단, ~1 = 0, ~0 = 1
1&1 = 1, 1&0, 0&1, 0&0 = 0
0|0 = 0, 0|1, 1|0, 1|1 = 1
1^1, 0^0 = 0 , 1^0, 0^1 = 1
이와 같다. 그럼 조금 더 정리해보자.
눈썹연산(XOR)에 대해서...

A^B의 비트 중, 값이 1인 임의의 비트의 서수를 d라 하자.
또한 값이 0인 임의의 비트의 서수를 s라 하자.
그러면
Ad^Bd = 1 = Cd
As^Bs = 0 = Cs
라 하면
Cd와 Ad의 관계는 다음과 같다.
Ad가 1이면 Ad^Cd = 0, Ad가 0이면 Ad^Cd = 1
Cs와 As의 관계는 다음과 같다.
As가 1이면 As^Cs =  1, As가 0이면 As^Cs = 0

따라서 A^C는 Ai == Bi인 비트들, 즉 As를 그대로 갖고, 그 외 Ai != Bi인 비트들, 즉 Ad는 그 반대인 Bd로 바뀌게 된다.
그러므로 그 결과는 B와 일치한다.

따라서 다음과 같은 성질이 증명되었다.
A^(A^B) = B


쉬프트 연산자.

A가 A1A2...An일 때,
A>>1는 AnA1A2...A(n-1)과 같다.
A<<1은 A2A3...AnA1과 같다.

A>>N은 for(int i=0;i<N;i=i+1;){A = A>>1}에서의 A와 같다.
다시말해, A>>N은 (A>>(N-1))>>1과 같다.

A<<N은 for(int i=0;i<N;i=i+1;){A = A<<1}에서의 A와 같다.
다시말해, A<<N은 (A<<(N-1))<<1과 같다.