[비트 연산] 기본

비트로 표현해서 풀면 편한 문제들이 많다.

이 페이지에서는 비트관련된 유용한 연산들을 소개한다.

비트 연산자들

a & b :and -> a & 7 = a % 8

a | b :or

a ^ b :xor  -> a ^ 0 = a 

~a   : not  

a << b : a를 b만큼 left shift

a >> b : a를 b만큼 right shift

비트를 이용한 집합의 표현

꽉 찬 집합을 표현하는 수를 생성하려면

  a = (1 << 30) - 1 // 30개의 비트가 모두 1로 채워진 값 구하기

원소를 하나 추가하려면 = 특정 위치를 1로 바꾸려면

  a |= (1 << p) //위치 p값을 1로 변경

원소를 하나 빼려면 = 특정 위치을 0으로 바꾸려면

  a &= ~(1 << p) //위치 p값을 0으로 변경

특정위치가 1인지 확인하려면

  if(a & (1 << p))

특정위치가 0인지 확인하려면

  if( !(a & (1 << p)) ) 

토글 (0이면 1로, 1이면 0으로)

  a ^= (1 << p ) //xor의 성질을 보면, 0과의 xor는 그 자신이, 1과의 xor는 토글

두 집합에 대한 연산

  added = a | b //합집합

  intersection = a & b //교집합

  removed = a & (~b) //차집합  a-b=a and (~b)

  toggled = a ^ b //a나 b중 한 곳에만 1이 있는

removed에 대해서 연산표를 그려보면,

a	b	~b	a & (~b)
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	0

  

집합의 크기(1인 비트 수)를 구하려면

int bitCount(int a){

         int cnt;

         for (cnt = 0; a; ++cnt)

                  a &= (a - 1);

         return cnt;

}

핵심: 어떤 수에서 1을 빼면, 가장 오른쪽에 있는 1인 비트가 사라지고 그 이하 비트가 1이 됨. 그 수와 and 연산을 하면, 가장 하위에 있던 비트 1이 0으로 바뀌게 됨

예를들어 a=01100의 경우, 

  cnt  a        a-1     a & (a-1)

 ------------------------

   0   01100

   1   01100  01011   01000

   2   01000  00111   00000

이렇게해서 1인 비트 수가 2임을 알 수 있음.

가장 최하위 비트를 구하려면

int firstOne = a & (-a);

핵심: a의 비트중 1인 최하위 비트를 구하는 것.  -a는 1의 보수로 처리된다. 즉, a의 각 비트를 반전시킨값에 +1을 하게 되는데, +1을 하게되면 오른쪽에서부터 시작해서 처음으로 만나는 0(이것이 원래수의 최하위 1인 비트)이 1로 바뀌고 거기까지의 1이 0으로 바뀐다. 따라서, a & (-a)를 하게되면 취하위 1인 비트만 남고 나머지는 0이된다. 

ex)     a = 1 0 1 0 0

       -a = 0 1 0 1 1 + 1  

           = 0 1 1 0 0

a & (-a)  = 0 0 1 0 0   

2의 거듭제곱인지 확인하려면

bool isPow2(int a){

         if (a & (a - 1)) return false;

         return true;

}

풀이: 2의 거듭제곱은 10, 100, 1000 등과 같이, 가장 왼쪽이 1이고 나머지는 0이다. a=100의 경우를 보면, a-1=011

a & (a-1) = 100 & 011 = 0 

즉, a-1의 경우 최하위 1이 0으로 바뀌고 그 아래 0들이 모두 1로 바뀌게 되는데, 2의 거듭제곱은 최상위 비트만 1이기에, 2의 거듭제곱수에 -1을 하면 01111 의 형태를 띄게되고, 이를 원래의 a와 &연산하면 당연 0이되야한다. 0이 아니라면 2의 거듭제곱이 아님.

모든 부분집합을 순회하려면

  for(s=a; s ; s = (s-1) & x) {

   ...

 }

테이블로 시뮬레이션해보면 다음과 같다.

a	s	s-1	(s-1)&a
10110	10110	10101	10100
	10100	10011	10010
	10010	10001	10000
	10000	1111	110
	110	101	100
	100	11	10
	10	1	0

Reference

1. 구종만. 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략. 인사이트. 

-끝-