[Algorithm] Bit Mask

HyunDong Lee·2022년 1월 7일
0

Algorithm

목록 보기
6/10
post-thumbnail

비트마스크

비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크라고 한다.

예를 들어서 10개의 스위치가 있다고 가정하면

switch = 0b10001100

이런식으로 정수형으로 나타낼 수 있다.

비트 마스크는

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

AND 연산 (&)

1로 구성된 숫자만 1로 반환한다.

bin(0b10100110 & 0b11011111)

OR 연산 (|)

둘 중에 하나만 1이어도 1로 바꾼다.

bin(0b1010 | 0b0101)

XOR 연산(^)

두 개 숫자가 다를 경우 1로 같으면 0

bin(0b0000 ^ 0b1100)

SHIFT 연산

a << b 는 sll a >> b는 srl

bin(0b0110 <<2) # 1000
bin(0b0110 >>2) # 0001, 1

NOT 연산(~)

bin(~0b1001)

비트연산 응용

원소 추가

n번 째 수를 추가할 때

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

원소 제거

n번 째 수 제거

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

원소 조회

있으면 1 없으면 0

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

원소 토글

n번째 비트가 1이면 0, 0이면 1로 바꾼다

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

0개의 댓글