비트마스크
비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크라고 한다.
예를 들어서 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, 1NOT 연산(~)
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
Grind