[알고리즘] 비트마스크(bitmask)

비트마스크(bitmask)

• 원소의 수가 많지 않을 때 사용
• 집합을 배열의 인덱스로 표현할 때 사용한다.
• 이진수로 비트 연산을 활용하는 방법

 

비트마스크 활용

• [1,2,3,4,5] 집합이 있을 때 부분 집합을 만든다.
• [1], [2], ... ,[1,2],[1,3], ... , [1,2,3], ... [1,2,3,4,5]
• 비트 마스크를 사용하면 각 요소를 인덱스로 표현하여 효율적인 접근이 가능하다.
• [1,2,3,4,5] -> 11111
• [2,3,4,5] -> 11110
• [1,2,5] -> 10011

 

비트의 연산

• AND, OR, NOT, XOR

A	B	~A(NOT)	A&B(AND)	A|B(OR)	A^B(XOR)
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

 

쉬프트(Shift) 연산자

• << : 왼쪽 시프트, A * 2^B, 0001 -> 0010 -> 0100 -> 1000 : 1 -> 2 -> 4 -> 8
• >> : 오른쪽 시프트, A / 2^B 1000 -> 0100 -> 0010 -> 0001 : 8 -> 4 -> 2 -> 1
• N&1 : N이 짝수인지 홀수인지 구하기 위해 2로 나눈 나머지를 1과 비교하는 연산, N%2==1

 

삽입, 삭제, 조회

• 삽입(OR)
  • 이진수가 10101일 때, i 번째 비트 값을 1로 변경하려고 한다. i=3일 때 변경 후에는 11101
  • 10101 | 1 << 3 
  • 10101 | 01000 = 11101
• 삭제(AND, NOT)
  • 11101 & ~1 << 3
  • 11101 & 10111 = 10101
• 조회(AND)
  • 10101 & 1 << i
  • 3번째 비트 값 : 10101 & 01000 = 0
  • 4번째 비트 값 : 10101 & 10000 = 10000

 

비트마스킹 문제 - 1094번 막대기

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

1094번: 막대기

x = int(input())
x = bin(x)
answer = 0
# 가지고 있는 막대 길이 모두 더하기
# 합이 X보다 크면 , 가장 길이 짧은 것을 절반으로 자르기
# 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같으면 위에서 자른 막대의 절반 중 하나를 버린다.

for i in x:
    if i == '1':
        answer += 1
print(answer)

 

비트마스킹 문제 - 11723번 집합

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

11723번: 집합

#M = 26 # 연산의 수
import sys
M = int(sys.stdin.readline())
S = 0 # 공집합

for _ in range(M):
    command = sys.stdin.readline().split()
    opt = command[0]
    if len(command)>1:
        x = int(command[1]) - 1

    if opt == 'add': # S에 x를 추가한다.
        S = S | (1 << x)
    elif opt == 'remove': # S에서 x를 제거한다.
        S = S & ~(1 << x)
    elif opt == 'check': # S에 x가 있으면 1을, 없으면 0 출력
        if S & (1 << x) == 0:
            print(0)
        else:
            print(1)
    elif opt == 'toggle': # S에 x가 있으면 x 제거, 없으면 x 추가
        S = S ^ (1 << x)
    elif opt == 'all': # S를 {1,2, ..., 20} 으로 바꾼다.
        S = (1 << 20)-1
    elif opt == 'empty': # S를 공집합으로 바꾼다
        S = 0