[C/C++] 비트마스크(BitMask)

 

 

비트(bit)

비트는 이진수(binary digit)로, 컴퓨터에서 사용되는 데이터의 최소 단위이다.

0 / 1 두 개의 값만을 가질 수 있으며, 이 두가지로 숫자를 표현하는 방법을 이진법이라고 한다.

 

 

 

비트 마스크
(BitMask)

비트마스크는 알고리즘 아닌 bit를 사용한 테크닉이다.

비트의 형태, 정수의 이진수 표현을 활용한 기법이다. 

 

비트를 이용하면, 

1. 0/1 true, false의 상태를 가진다. 
2. 이진수를 십진수로 표현할 수 있다.

 

 

비트마스크의 활용

 

 

집합구현

N비트 정수라면, N개의 원소를 가지는 부분집합을 모두 표현할 수 있다.

백준 알고리즘 11723번 문제 "집합" - https://www.acmicpc.net/problem/11723

11723번: 집합

 

다음과 같은 집합의 부분집합을 표현할 때,

{0, 1, 2, 3, 4}

 

1의 방법으로 표현하면, 다음과 같이 존재하는 인덱스로 표현할 수 있고

{0, 1, 2, 3, 4} = 1 1 1 1 1

{0, 2} = 0 0 1 0 1

{2, 3, 4} = 1 1 1 0 0

 

2의 방법으로 표현하면, 다음과 같이 표현할 수 있다.

{0, 1, 2, 3, 4} = 1 1 1 1 1 = 31

{0, 2} = 0 0 1 0 1 = 5

{2, 3, 4} = 1 1 1 0 0 = 28

 

 

 

BitField를 이용한 DP(동적계획법)

ㄹㄹㄹ

 

 

비트 연산자

비트 연산자는 비트 단위 연산을 수행하는 연산자이다.

 

AND(&)

두 연산자의 특정 비트가 1일 때, 연산 결과는 1이다.

*&& :  둘다 참(1)이어야 참(1)

a의 비트	b의 비트	a & b
0	0	0
0	1	0
1	0	0
1	1	1

 

OR(|)

피연산자의 같은 위치에 있는 비트 중 하나라도 1이면 연산 결과의 해당 비트가 1이 된다.

*|| : 둘 중 하나만 참이어도 참

a의 비트	b의 비트	a & b
0	0	0
0	1	1
1	0	1
1	1	1

 

 

XOR(^)

XOR : 배타적 논리합(exclusive OR)

두 값이 다르면1, 같으면 0이 되는 연산이다.

a의 비트	b의 비트	a & b
0	0	0
0	1	1
1	0	1
1	1	0

 

 

NOT(~)

피 연산자가 1개인 단항 연산자, 각 비트를 반전시킴 

a의 비트	~a의 비트
0	1
1	0

 

 

 

SHIFT

첫번째 피 연산자의 각 비트를 두 번째 피 연산잔가 지정하는 만큼 오른쪽/왼쪽으로 shift하는 연산 

10<<2 : 10을 왼쪽으로 2비트 이동 

 

<< n

n비트씩 왼쪽으로 이동, 왼쪽으로 밀려난 비트가 사라지고, 오른쪽 빈자리에는 0이 채워진다.

결과는 2^n을 곱한 것과 같다.

 

 

>> n

오른쪽으로 밀려난 비트가 사라지고, 왼쪽 빈자리에는 부호 비트가 채워진다. 

(양수는 0으로 채워지고, 음수는 1로 채워진다. 만약, 이동 연산자의 좌변이 부호 없는(unsigned) 정수형이면, 0으로 채워진다.)

결과는 2^n으로 나눈 것과 같다. 

 

 

<참고>

https://mygumi.tistory.com/361

비트마스크(BitMask) 는 무엇인가? :: 마이구미

https://rebro.kr/63

비트마스크 (BitMask) 알고리즘

 

 

<관련 문제>

백준 알고리즘 2098번 문제 "외판원 순회" - https://www.acmicpc.net/problem/2098

백준 알고리즘 11723번 문제 "집합" - https://www.acmicpc.net/problem/11723

백준 알고리즘 12813번 문제 "이진수 연산" - https://www.acmicpc.net/problem/12813