[C++] 비트 연산과 비트마스킹

썸네일

비트마스킹을 알고리즘 문제를 풀 때 어떻게 활용하는지 알아보기 전에 비트연산자를 먼저 알아보자.

비트연산자

연산자	기능
&	AND 연산
|	OR 연산
^	XOR 연산
~	모든 비트를 반전
<<	비트 열을 왼쪽으로 이동
>>	비트 열을 오른쪽으로 이동

& 연산자

true & true = true이고, 나머지는 모두 false를 반환한다

연산	결과
0 & 0	0
1 & 0	0
0 & 1	0
1 & 1	1

ex) 1001 & 1000 = 1000

 

| 연산자

하나라도 true라면, true를 반환한다.

연산	결과
0 & 0	0
1 & 0	1
0 & 1	1
1 & 1	1

ex) 1001 & 1000 = 1001

 

^ 연산자

두 비트가 서로 다를 경우(true ^ true, false ^ false)에 true를 반환한다.

연산	결과
0 & 0	1
1 & 0	0
0 & 1	0
1 & 1	1

ex) 1001 ^ 1000 = 0001

ex2) 1001 ^ 1010 = 0011

 

~ 연산자

보수 연산이라고도 불리며 0을 1로, 1을 0으로 반전시킨다.

-x = ~x+1이 된다.

이진수를 음수로 표현할 때, 비트를 반전시키고 1을 더하여 구한다.

연산	결과
~0	1
~1	0

 

<< 연산자

비트를 한 칸씩 왼쪽으로 옮긴다.

40 << 1은 1칸, 40 << 2는 2칸을 옮긴다는 것을 의미한다.

$$  a << b = a*{2}^{b} $$

그러므로 40 << 1 = 40 * 2 ^ 1 = 80이다.

 

비트마스킹에서는 주로 lvalue가 1인 1 << b 로 자주 사용한다.

ex) 1 << 4 = 10000

출처:&nbsp;https://byjus.com/gate/left-shift-operator-in-c/

 

>> 연산자

비트를 한 칸씩 오른쪽으로 옮긴다.

$$ a >> b = a*({\frac{1}{2}})^{b} $$

출처:&nbsp;https://byjus.com/gate/right-shift-operator-in-c/

 

비트 연산 활용

비트를 키는 것은 1로 만든다, 비트를 끄는 것은 0으로 만든다는 의미이다.

이 때, idx는 맨 뒤가 0이며 왼쪽으로 갈수록 1씩 커진다.

idx번째 비트 끄기	S & = ~(1 << idx)
idx번째 XOR 연산	S ^= ~(1 << idx)
최하위 켜져있는 비트 찾기	idx = (S & -S)
크기가 n인 집합의 모든 비트를 켜기	(1<<n) - 1
idx번째 비트 켜기	S |= (1 << idx)
idx번째 비트가 켜져 있는지 확인하기	if(S & (1 << idx))

 

idx번째 비트 끄기

S & = ~(1 << idx)

10010이 있을 때 뒤에서 2번째 비트를 꺼보자.

10010 & = ~(1 << 1)은

10010과 ~(1 << 1)을 AND 연산을 하는 것이다.

~(1 << 1) = ~(00010) = 11101 이므로,

10010 & = ~(1 << 1)은 10010 & 11101 = 10000이다.

 

idx번째 XOR 연산

S ^= ~(1 << idx)

idx번째 비트가 1이면 0으로, 0이면 1로 반전되도록 구현할 수 있다.

10010 ^ = ~(1 << 1)

= 10010 ^ 00010

= 10000

 

최하위 켜져있는 비트 찾기

idx = (S & -S)

10010에서 최하위 켜져있는 비트는 idx=1일 때이다.

-x = ~x+1이므로

-(10010) = ~(10010)+1 = 01101 + 1 = 1101110 이다.

 

10010 & 1101110

= 0010010 & 1101110 

= 0000010

이므로

1번째 비트가 최하위 켜져있는 비트임을 비트 연산으로 구할 수 있다.

 

크기가 n인 집합의 모든 비트 켜기

(1<<n) - 1

n=4일 때를 예시로 들면,

(1 << n) - 1

= 10000 - 1

= 01111 = 1111

이다.

 

idx번째 비트 켜기

S |= (1 << idx)

10010이라는 수가 있을 때 0번째 비트를 켜보자.

1 << 0 = 1 = 00001 이므로

10010 | 00001

= 10011

이다.

 

idx번째 비트카 켜져있는지 확인하기

if(S & (1 << idx))

10010에서 3번째 비트와 4번째 비트가 켜져있는지 확인해보자.

 

10010 & (1 << 3)

= 10010 & 01000

= 00000 = 0

이므로 3번째 비트는 꺼져있다는 것을 알 수 있다.

 

10010 & (1 << 4)

= 10010 & 10000

= 10000

이므로 4번째 비트가 켜져있는 것을 알 수 있다.

 

비트마스킹 알고리즘

이제 비트마스킹을 위해 필요한 개념들을 배웠다.

비트마스킹은 boolean 배열의 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색, 수정 등의 작업을 하는 것이다.

 

친구 4명 중, A와 C는 영화를 보러 가고 싶고, B와 D는 아닌 상황을 가정해보자.

기존에는 vector<bool>, bitset, set<int> 등의 자료구조를 사용하여 문제를 구현할 것이다.

하지만 비트마스킹을 사용한다면 위 상황을 1100이라고 나타내어, 숫자가 배열의 역할을 할 수 있게 된다.

 

2^30이 10억이므로 시간복잡도 때문에 비트마스킹은 주로 n=30~31일 때까지 한다.

 

왜 비트마스킹이라고 할까?
컴퓨터에서 메모리의 용량을 표현하는 최소 단위가 비트(bit)이며 이는 0 또는 1의 값을 가진다.
이를 기반으로 해당 비트를 켜거나(1) 끄거나(0) 마스킹하기 때문에 비트마스킹이라고 한다.

 

Reference

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의

4. C 비트연산자(연산자 &, |, ^, ~, <<, >>, and, or, xor, 비트 반전, 비트 이동)