비트마스크 정리

비트 마스크란?

비트 연산을 통해서 부분 집합을 표현하는 용도로 사용

두 수 A,B를 비트 연산할 경우에는 가장 뒤의 자리부터 하나씩 연산을 수행하면 됩니다.

예를 들어 A= 27 , B=83일 경우,

A = 11011(2) 

B = 1010011(2) 

여기서 A & B를 계산하면 뒤의 자리부터 맞춰서 계산해야 하므로 

   0011011(2) 

& 1010011(2)

ㅡㅡㅡㅡㅡㅡㅡㅡ 

이렇게 연산 되어서 동일하게 1이 있으면 1로 반환되고 0,1 로 비교될 경우는 0으로 반환된다.

그래서 값은 19가 나온다.

이렇게 뒤의 자리부터 맞춰서 계산해야 한다.

비트 연산

Shfit Left ( << )

 A << B ( A를 왼쪽으로 B 비트만큼 민다. )

예 :) 

1 << 0  : 1

1 << 1  : 10(2) --> 2

1 << 2 :  100(2) --> 4

3 << 4  : 110000(2) --> 2^4 + 2^5 = 48

Shfit Right ( >> )

 A >> B ( A를 오른쪽으로 B 비트만큼 민다. )

1 >> 0 :  1 

1 >> 1 :  0 

10 >> 1 : 1010(2) --> 0101(2) : 5 (2^2 + 2^0)

10 >> 2 : 1010(2) --> 0010(2) : 2 (2^1)

10 >> 3 : 1010(2) --> 0001(2) : 1 (2^0)

비트 연산을 통해 얻은 새로운 공식(개념)

---

A << B 는 A * 2^B와 같다.

A >> B 는 A / 2^B와 같다.

(A + B) / 2 는 (A+B) >> 1과 같다. 

홀수 판별 식 

if(N % 2 == 1) 을 다음과 같이 사용할 수 있다.

if(N & 1) 

N이 10이라 한다면 1010(2) 이고 1은 0001(2) 이기 때문에 and 연산을 했을 때 일치하면 참 (홀수다.) 

일치하지 않으면 거짓 (짝수다.)

판단할 수 있다.

N을 이진수로 바꾸었을 때 마지막 수에서 1이 있으면 홀수이기 때문에 가능한 개념이다.

---

N에서 x의 수가 포함되어 있는지 검사하는 방법

" & 연산 " 을 하면 됩니다.

예시

N = 570

• 570에서 0이 포함되어 있는지 검사하기.

570 & 2^0 ( 1 << 0 : 2^0 ) = 0 

• 570에서 3이 포함되어 있는지 검사하기.

570 & (1 << 3 : 2^3) = 8

( 1 << 3 ==> 0000001000(2) 이기 때문에 2^3 자리만 남아서 비교하게 됩니다. 

따라서 2^3 자리가 존재할 경우 '& 연산'을 통해서 존재함의 여부를 확인한다.)

N에서 x의 수를 추가시키는 방법은 다음과 같습니다.

" | 연산 " 을 하면 됩니다. 

 

• 570에 3 추가하기 

0 또는 1을 비교할 때 or 연산을 하게 되면 추가되게 되므로 | 연산을 사용하는 것입니다.

570 | 2^3 ( 1 << 3 ) = 570 

• 574에 4를 추가하기 

574 | 2^4 ( 1 << 4 ) = 1000111010(2) = 570

N에서 x의 수를 제거시키는 방법은 다음과 같습니다.

" & ~ 연산 " 을 하면 됩니다. 

제거한다는 것은 N에 예를 들어 3이 존재할 경우 이진수로 변환했을 때 2^3 자리에 1이 있는 것이다.

2^3 자리에 있는 1을 제거하기 위해서는 1과 0을 '& 연산' 을 하면 됩니다.

따라서 2^3을 비교할 때 비교하는 3도 이미 존재한다는 전제하에 비교하기 때문에 

아래와 같은 공식이 만들어진다.

         570 = 1000111010(2)   --> 1000111010(2)

&   ~(1<<3) = 0000001000(2) --> 1111110111(2)

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

                                   1000110010(2)

답 : 562 

결국 3의 자리 (1 << 3)의 자리는 제거가 된 것을 확인할 수 있다.

• 전체 집합

(1 << N) -1 

• 공집합 

0

<최종 정리> 

• 현재 집합이 S일 때 
  
  
  1. i 를 추가 

S = S | ( 1 << i )

  

2. i 를 검사

S = S & ( 1 << i )

3. i 를 제거 

S = S & ~( 1 << i )

4. i 를 토글 ( 0 --> 1 / 1 --> 0 )

S ^ ( 1 << i ) 

< 예제 BOJ 11723 > 

import java.io.StringWriter;

import java.util.Scanner;

public class 비트마스크2 {

static Scanner scanner;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

StringWriter answer = new StringWriter();

int N = scanner.nextInt(); // 입력 횟수 정리하기

int bit_set = 0;

while (N > 0) {

String str = scanner.next();

if ("add".equals(str)) {

int nm = scanner.nextInt();

bit_set = bit_set | (1 << nm);

} else if ("remove".equals(str)) {

int nm = scanner.nextInt();

bit_set = bit_set & ~(1 << nm);

} else if ("toggle".equals(str)) {

int nm = scanner.nextInt();

bit_set = bit_set ^ (1 << nm);

} else if ("check".equals(str)) {

int nm = scanner.nextInt();

if ((bit_set & (1 << nm)) == 0) {

// 존재하지 않는 경우

answer.append("0\n");

} else {

answer.append("1\n");

}

} else if ("all".equals(str)) {

bit_set = (1 << 21) - 1; // 전체 수가 21이므로

bit_set = bit_set & ~(1); // 1의 반대는 0이므로 어차피 앞서서 1뺏는데 ..

} else if ("empty".equals(str)) {

bit_set = 0;

}

N--;

}

System.out.println(answer);

}

}