[인프런] 비트 마스킹

📘 10주완성 C++ 코딩테스트 강의를 수강한 후 정리한 글입니다.

※ 비트 연산자 활용법

1. idx번째 비트 끄기

 

ex)

S = 10010 (18) 에서 1번째 비트를 끄려면,

 

먼저 00010을 만든다. ( 1 << 1 )

 

그 다음 해당 비트를 뒤집는다.11101

 

여기서, S = 10010과 & 연산을 하면,

10010
&
11101 =
10000 이 된다.

 

 

따라서,

idx번째 비트 끄기 : S &= - (1 << idx )

 

 

코드

#include <bits/stdc++.h>
using namespace std;
int main(){
int S = 18;
    int idx = 1;
    S &= - ( S << idx );
    cout << S << '\n'; //16
    return 0;
 }

 

 

2. idx번째 비트 XOR 연산 

: 해당 비트가 0이면 1, 1이면 0으로 만든다.

 

S = 10010 (18)

 

ex 1) 1번째 비트 0으로 만들기.

 

먼저 1 << 1 을 통해 00010 을 만든다.

 

10010 
^
00010 =
10000

 

ex 2) 0번째 비트 1로 만들기.

 

1 << 0 = 00001

 

10010
^
00001 = 
10001

 

 

따라서,

idx번째 비트 XOR 연산 : S ^= ( 1 << idx )

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main(){
int S = 10;
    int idx = 1;
    S ^= ( 1 << idx );
    cout << S << '\n'; //16
    return 0;
 }

 

3. 최하위 켜져있는 비트 찾기

 

10010 : 최하위 켜져있는 비트 = 1번째 비트

10000:  최하위 켜져있는 비트 = 4번째 비트

→ 오른쪽에서부터 탐색하여 1을 찾아서 해당 인덱스를 찾으면 된다.

 

ex)

S = 10010

 

~ S = -  (S + 1) 이기 때문에,

01101 + 1 =  - S

01110 = - S

 

01110
&
10010=
00010

 

 

최하위 켜져있는 비트 찾기:  idx = (S & -S)

 

 

코드

#include <bits/stdc++>
using namespace std;

int main(){
int S = 18;
	int idx = ( S & -S );
    cout << idx << '\n'; //2
    return 0;
 }

 

 

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

배열 크기가 4인 집합을  [1,1,1,1]이 아닌, 15로 "표현" 할 수 있다.

 

크기가 4라면

16(1<< 6) 이 되고

(1<<4) - 1 = 15(1111) 가 된다.

 

따라서,

크기가 n인 집합의 모든 비트를 켜기 : ( 1 << n ) - 1

 

 

코드

#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 4;
	cout << ( 1 << n ) - 1 << '\n' ; //15
    return 0;
}

 

5. idx번째 비트를 켜기

 

ex)

S = 10010(18) 에서, 0번째 비트를 키면

10011(19)가 된다.

 

1 << 0 = 00001 과 S를 OR 연산을 하면

10010
|
00001 =
10011

 

따라서,

idx번째 비트를 켜기 : S |= ( 1 << idx )

 

코드

#include <bits/stdc++>
using namespace std;
int main(){
int S = 18;
	int idx = 0;
    S |= ( 1 << idx );
    cout << S << '\n' ; //19
    return 0;
}

 

 

6. idx번째 비트가 켜져있는지 확인하기

 

ex)

S = 10010에서 3번째 비트가 켜져있는지 확인하려면

10010
&
00100 = 
00000

결과 값이 0이므로 False가 된다.

 

따라서,

idx번째 비트가 켜져있는지 확인하기 : if(S & ( 1 << idx))

 

 

코드

#include <bits/stdc++.h>
using namespace std;
int main(){
int S = 10;
	int idx = 0;
    if( S & ( 1 << idx ))
    	cout << "해당 idx :" << idx << "가 켜져있습니다.\n";
   	else
    	cout << "해당 idx :" << idx << "가 꺼져있습니다.\n";
        
    return 0;
 }

 

비트마스킹 : 경우의 수, 매개변수

 

어떤 특정원소를 찾을 때의 시간 복잡도.

- 배열의 어떤 요소를 찾을 때 선형적인 시간 : O(N)

- sorted array에서 이분탐색으로 찾을 때 : O(logN)

- 해싱테이블 : O(1)

 

vector<bool>, bitset, set<int>로 표현해서 무언가를 찾는 연산을 하지만, 비트 연산을 쓰면 가볍고 빠르게 할 수 있다.

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

 

비트마스킹을 이용한 경우의 수

ex) { 딸기, 사과, 포도 배 }의 모든 경우의 수는?

각각의 요소는 2개의 상태값(포함, 불포함) 을 갖기 때문에 16가지의 경우의 수가 있다.

 

#include <bits/stdc++.h>
using namespace std;

const int n = 4;

int main()
{
string a[n] = {"사과", "딸기", "포도", "배"};
	for(int i = 0; i < ( 1 << n ); i++)
    {
   		string ret = "";
        for(int j = 0; j < n; j++){
        	if(i & ( 1<<j)){
            	ret += (a[j] + " ");
        }
        
     }
     
     return 0;



}