비트마스크

비트 마스크란?

정수의 이진수 표현을 자료구조로 사용하는 기법이다.

비트마스크 용어

비트가 켜져 있다 : 1

비트가 꺼저 있다 : 0

비트마스크 장점

(1)적은 메모리 사용

(2)빠른 수행 시간

    ●원소가 많으면 사용 할 수 없지만 원소가 작을때 매우 빠른 속도로 연산가능하다

비트연산자

(1)A&B = AND연산

(2)A|B = OR연산

(3)A^B =XOR연산

(4)~A = NOT연산

(5)a<<b = 정수 a를 b비트 왼쪽 시프트

(6)a>>b = 정수 a를 b비트 오른쪽 시프트

비트마스크 규칙

(1)A<<B ==  A*2^B

(2)A>>B ==  A/2^B

이 규칙을 알 수 있다.

비트마스크 집합 예

EX){1,2,3,6,8} -> 10100111(2) = 333

비트마스크 백준 11723 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Code_11723_YES
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(buffer.readLine());
        StringBuilder builder = new StringBuilder(); //시간초과 나므로

        int figure = 0; //수 담기
        int change = 0; //반복문 마다 받는 변수

        for (int i=0; i<number; ++i)
        {
            String[] temp = buffer.readLine().split(" ");
            String calculator = temp[0]; if (temp.length == 2) change = Integer.parseInt(temp[1]);

            if (calculator.equals("add"))
                figure = figure | (1 << change);
            else if (calculator.equals("remove"))
                figure = figure & ~(1 << change);
            else  if (calculator.equals("check"))
            {
                if ((figure & (1 << change) ) > 0 )// 존재 하면 -> 원래1로 했는데 존재하면 그 수를 반환하므로 >0으로 함
                    builder.append(1).append("\n");
                else //존재 하지 않는 다면
                    builder.append(0).append("\n");
            }
            else if(calculator.equals("toggle"))
                figure = figure ^ (1 << change);
            else if (calculator.equals("all"))
                figure = ((1 << 21)-1) & ~(1); //전체수가 21개이므로 21개 지정함
            else if (calculator.equals("empty"))
                figure =0;
        }
        System.out.println(builder);
    }
}