[JAVA] 비트마스킹(Bit Mask) 이해하기

 

 

목차

 

1. 비트마스크란?

 

2. 비트마스크의 예시

 

3. 비트 연산자

 

 

 

| 비트마스크(Bit Mast)란?

 

비트마스크는 알고리즘이 아닌 하나의 기법으로

정수를 이진수로 표현하고, 비트연산으로 다양한 문제를 해결해나가는 방법이다. 

 

 

| 비트마스크 예시

 

예를 들어

열쇠가 a , b , c , d , e , f로 6개가 있다고 가정한다. 

이때, 가지고 있는 열쇠가 a , c , e 일때, 

 

 

위와 같이 표현할 수 있다.

이 예시에서는 열쇠를 가지고 있는 경우/가지고 있지 않은 경우(1/0) 를 비트마스크로 표현하였는데,

 

이 경우 이외에도

 

스위치를 켜거나 끄는 경우,

해당 위치에 방문했거나 아직 방문하지 않는 경우 등

 

더욱 다양한 상황에서도 적용이 가능하다.

 

여기서 알 수 있는 점은 비트마스크는 이진수를 이용하여 두 가지 정보를 표현한다는 것이다.

-> 1 또는 0(true 또는 false)

-> 이렇게 생성한 이진수는 십진수로도 표현 가능

 

 

 

 

그리고 비트마스크의 상태를 변경(제어)시키기 위한 다양한 연산을 비트연산으로 수행할 수 있다.

 

 

| 비트마스크 연산자

 

비트 연산자는 비트(bit) 단위로 논리 연산을 할 때 사용하는 연산자로

 

AND, OR, XOR, NOT, SHIFT 

 

다섯 가지를 소개하려고 한다.

 

1. AND

& : 대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산)
00001111 & 00010101 = 00000101

 

2. OR

| : 대응되는 비트 중에서 하나라도 1이면 1을 반환함. (비트 OR 연산)
00001111 | 00010101 = 00011111

 

3. XOR

^ : 대응되는 비트가 서로 다르면 1을 반환함. (비트 XOR 연산)
00001111 ^ 0001010101 = 00011010

 

4. NOT

~ : 비트를 1이면 0으로, 0이면 1로 반전시킴. (비트 NOT 연산)
~00001111 = 11110000

 

5. 시프트 연산자

<< : 지정한 수만큼 비트들을 전부 왼쪽으로 이동(이동되고 남은 비트는 0으로 채움)시킴. (left shift 연산)
>> : 부호를 유지(이동되고 남은 비트는 부호 비트로 채움)하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴. (right shift 연산)

00001010 << 2 = 101000  (곱하기 2)
00001010 >> 2 = 000010  (나누기 2)

 

 

 

https://www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

 

백준에 위 그래프문제를 풀면서 비트마스킹을 급하게 사용해보았다.

그리고 문제를 다 푼 후에 추가적으로 공부를 해야겠다는 생각이 들어서 

공부하면서 차근차근 정리해보았다.

 

 

백준에 달이 차오른다, 가자. 는 그래프 이론과 함께 풀어야 하기 때문에 난이도가 꽤 있는 문제였고,

 

 

아래에 부분수열의 합을 비트마스크로 연습해보면 좋을 것 같다.

 

 

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

 

 

 

★1182번: 부분수열의 합 해설

 

https://hailey-v.tistory.com/24

[JAVA]백준 1182번: 부분수열의 합