[Algorithm] 재미있는 비트 연산

★프로그램에서 사용되는 n비트 정수는 내부적으로 n개의 비트로 이루어진 이진수형태로 저장된다. 예를들어 자바의 int형은 32비트로 이루어진 이진수의 형태이며 2^32개의 수를 표현할 수 있다.

★32비트 정수형은 부호가 없는(unsigned) 정수의 경우 0(32개의 비트가 모두 0)부터 2^32-1(32개의 비트가 모두 1)까지를 표현할 수 있다.

★부호가 있는 32비트 정수형은 맨 앞의 1자리를 비트로 사용하고(0은 양수, 1은 음수) 나머지 31자리를 수로 크기를 나타낸다. 따라서 부호가 있는 32비트 정수는 -2^31부터 2^31-1까지를 나타낼 수 있다.

★절대값은 같으면서 서로 반대의 부호를 가진 두 정수는 -x = ~x + 1의 관계가 성립한다. 모든 부호를 뒤집은 후 1을 더하면 부호가 뒤집힌다는 이야기인데 이런 방법을 2의 보수법이라고 한다.

★부호를 제외한 31자리의 수는 -2^31부터 -1까지의 범위(음수의 범위)와 0부터 2^31-1까지가 대응된다. 값이 커질때 절대값도 같이 커지게 된다. 만약 부호가 있는 4비트의 정수를 예로 들면 1000(-2^3) 부터 가장 큰 음수인 1111(-1)까지 1씩 증가하다 1을 더하면 0000이 되는데, 이렇게 해야 -1에 1을 더하여 자연스럽게 0이 되도록 한 것이다. 또한 가장 큰 양수 0111(2^3-1)에 1을 더하면 1000(-2^3)이 되어 오버플로우가 일어나게 된다.

★비트 연산

1. And연산 a & b : a와 b에 공통으로 비트1이 있는 자리에 1이 들어간 정수를 만듬. 이 연산을 이용해 홀수와 짝수를 판단할 수 있다. 정수 비트의 맨 뒷자리가 1이면 홀수, 0이면 짝수이기 때문에 a & 1가 1이면 홀수, 0이면 짝수인 것이다. 이를 일반화 하면 x & (2^k - 1)가 0일때 x는 2^k로 나누어 떨어진다. 예를 들어 8비트 부호있는 정수 40(= 0010 1000)과 7(= 2^3 - 1, 0000 0111)을 and연산하면 0이기 때문에 정수 40은 8(2^3)에 나누어 떨어진다. 이 방법은 나누는 수가 2^k일 때만 사용할 수 있다. (홀짝 판별하기를 2로 나눈 나머지를 활용하는 흔한 방법과 실행시간을 비교해 봤는데 그다지 차이가 없었다.)

2. Or연산 a

   b : a와 b중 하나만 1이면 그 자리에 1이 들어간 정수를 만듬.

3. Xor연산 a ^ b : 거듭제곱하는 연산자가 아님. a와 b중 하나만 1인 경우에만 그 자리에 1이 들어가는 정수를 만든다. 그러니까 a와 b의 비트가 다른 경우 1이 들어간다. 1111 1111 ^ 1111 0101은 0000 1010이다.

4. Not연산 ~a : 모든 비트를 뒤집는다. 위에서 부호 바꾸는 방법에 -x = ~x + 1이라고 했으므로 ~x = -x - 1이 성립한다.

5. 시프트 연산 a « b 또는 a » b : a의 비트를 왼쪽(«)또는 오른쪽(»)으로 b칸 밀어내는 연산이다. 왼쪽 시프트 연산의 경우 b가 1 늘어날 수록 a는 2배가 되고(이진수니까) 반대로 오른쪽은 b번 2로 나눈것과 같다(나머지가 있는 경우는 버린다).

★비트마스크 1 « b : b번째의 비트에만 1이 있고 나머지는 0인 정수가 된다. 8비트 정수에서 1 « 3은 0000 1000이다. 이를 이용해 정수의 특정한 비트에 접근할 수 있게 된다.

1. x & (1 « k) : 연산의 결과가 0이면 정수 x의 k번째 자리는 0이고, 결과가 0이 아니라면 정수 x의 k번째 자리는 1이라는 의미이다. 이 연산을 이용하면 정수의 이진수 확인을 쉽게 할 수 있다.(변환은 아니고 확인임) String out = “”; for (int i = 0; i < 32; i++) { char c = ((1 « i) & n) == 0 ? ‘0’ : ‘1’; out = c + out; } System.out.println(out);

2. x =	(1 « k) : x의 k번째 비트를 1로 바꾼다.

3. x =& ~(1 « k) : x의 k번째 비트를 0으로 바꾼다.
4. x =^ (1 « k) : x의 k번째 비트를 뒤집는다.
5. x =& (x - 1) : x의 가장 오른쪽 비트 1을 0으로 바꾼다.
6. x =& -x : x의 모든 비트를 0으로 바꾸되, 비트 1중에서 제일 오른쪽 것만 하나 남긴다.

7. x =	(x - 1) : 마지막 비트 1 다음에 나오는 모든 비트를 뒤집는다.

8. x가 양의 정수일 때 x & (x - 1) : 결과가 0이면 x는 2의 거듭제곱수이다.

★참고로 자바에서 비트연산은 비교연산보다 우선순위가 낮으므로 괄호를 신경써서 쳐야한다.

★비트마스크 연산에서 (1 « k)는 기본적으로 int형임을 주의한다.

★정수가 n비트의 이진수라는 점을 이용해 집합 {0, 1, …, n-1}의 모든 부분집합을 표현할 수 있다. k번째 이진수가 1이라면 부분집합에 k가 속해있다는 의미가 된다. 집합 {0 .. 32}의 부분집합을 정수를 이용하여 넣고 확인하고 제거해보자.

★이러한 정수 2개(즉 집합 2개, a와 b)로 집합에 대한 연산을 할 수 있다

1. a & b : 교집합연산

2. a

   b : 합집합연산

3. ~a : 여집합연산
4. a & (~b) : 차집합, a - b연산

★연습문제 : 앞의 부분집합 만들기 문제를 list가 아닌 32비트 정수를 이용해 다시 풀어보자.

※이 포스트는 안티 라크소넨의 책 알고리즘 트레이닝 2장을 참고하였습니다.