1.비트 마스크

컴퓨터는 내부적으로 bit 단위로 연산을 한다. bit는 모두 익히 알 듯이 0과 1로만 이루어져 있는데 이 특징을 이용해서 다양한 알고리즘 문제에서 간결한 코드와 빠른 속도로 활용이 가능하다.

• 일반적 표현

switch_states = [True, False, False, True, True, False, False, False, True, True]

• 정수형표현 (비트마스크)

switch_states = 0b1001100011  # 611, python에서는 앞에 '0b'를 붙여 이진수 표현 가능

2. 비트 마스크의 장점

• 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐
• 더 간결한 코드 작성이 가능
• 더 빠른 연산이 가능
• 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함.

3. 비트 마스크 구현

AND 연산 (&)

대응하는 숫자가 모두 1일 경우 1을 반환합니다.

0b1010011010 & 0b1101101100  # 0b1000001000

OR 연산 (|)

대응하는 숫자중 하나라도 1일 경우 1을 반환합니다.

0b1010011010 | 0b1101101100  # 0b1111111110

XOR 연산 (^)

대응하는 숫자가 서로 다를 경우 1을 반환합니다.

0b1010011010 ^ 0b1101101100  # 0b111110110

SHIFT 연산 (>>, <<)

a << b는 a의 비트를 b칸 만큼 왼쪽으로 밀어 내는 것이고, a >> b는 a의 비트를 b칸 만큼 오른쪽으로 밀어내는 것 입니다.

0b0010 << 2  # 0b1000
0b1100 >> 2  # 0b11

NOT 연산 (~)

비트 값을 반전시킵니다.

~0b0010 << 2  # 0b1101

비트 연산 응용

원소 추가

n번째 수를 추가 하고자 할 때

n = 3
0b0010 | (1 << n)  #  0b1010

원소 제거

n번째 수를 제거 하고자 할 때

n = 3
0b1010 & ~(1 << n)  #  0b10

원소 조회

n번째 수가 있나 없나 확인 할 때 (0이면 없고, 1 이상이면 있는 것)

n = 3
0b1010 & (1 << n)  #  0b1000

원소 토글

n번째 수를 켜져 있으면 끄고, 꺼져 있으면 켬

n = 3
0b1010 ^ (1 << n)  #  0b10

참고문헌

https://velog.io/@1998yuki0331/Python-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9-%EC%A0%95%EB%A6%AC
https://justkode.kr/algorithm/bitmash