비트마스크(bitmask)란 무엇인가?
bit 연산을 이용한 소소한 테크닉 2020-06-16
주의! Caution!
해당 게시글은 Archive된 게시글 입니다.
Archive된 사유는 다음 중 하나에 해당 됩니다.
  • 작성 된지 너무 오랜 시간이 경과 하여, API가 변경 되었을 가능성이 높은 경우
  • 주인장의 Data Engineering으로의 변경으로 질문의 답변이 어려워진 경우
  • 글의 퀄리티가 좋지 않아 글을 다시 작성 할 필요가 있을 경우
이 점 유의하여 게시글을 참고 하시길 바랍니다.

밑 예제 들은 Python으로 작성 되었습니다.

나름 짧은 서론

거두절미 하고 이야기 하면, 비트마스크는 알고리즘 이라기 보단 테크닉에 가깝습니다. 비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술비트마스크 라고 합니다.

예를 들어 보겠습니다. 10개의 스위치가 있다고 가정하고, 우리는 이 10개의 스위치 상태를 표현 하고 싶습니다! 당연히 스위치는 on/off 만 존재 할 것입니다. 이를 list 형태로 표현하면.

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

하지만, 이는 2진수의 숫자 로도 표현 할 수 있지 않을까요?

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

이렇게 정수형으로 나타내면 장점이 다양합니다.

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

비트 연산

AND 연산 (&)

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

bin(0b1010011010 & 0b1101101100)  # 0b1000001000

OR 연산 (|)

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

bin(0b1010011010 | 0b1101101100)  # 0b1111111110

XOR 연산 (^)

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

bin(0b1010011010 ^ 0b1101101100)  # 0b111110110

SHIFT 연산 (>>, <<)

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

bin(0b0010 << 2)  # 0b1000
bin(0b1100 >> 2)  # 0b11

NOT 연산 (~)

비트 값을 반전시킵니다.

bin(~0b0010 << 2)  # 0b1101

비트 연산 응용

원소 추가

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

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

원소 제거

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

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

원소 조회

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

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

원소 토글

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

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

풀만한 알고리즘 문제

연습

실전

Algorithm Knowledge 시리즈의 다른 글
Recent Posts in Algorithm Category