비트마스킹(Bit Masking)

비트마스킹 (Bit Masking)

비트마스킹은 정수를 이진수로 표현해서 특정 상태를 관리하는 기법이다.

보통 비트 연산자를 활용해서 데이터를 조작한다.

 

0b10101(십진수 21)처럼 이진수로 보면, 각각의 자리가 어떤 상태를 나타내는 플래그가 될 수 있다.

• 1 이면 "켜짐" (True, ..)
• 0 이면 "꺼짐" (Flase, ..)

📌 비트 연산자 정리

연산자	설명	예시 (A=0b1010, B=0b1100)	결과
& (AND)	둘 다 1이면 1	A & B	0b1000 (8)
`	`(OR)	하나라도 1이면 1	`A
^ (XOR)	다르면 1, 같으면 0	A ^ B	0b0110 (6)
~ (NOT)	비트 반전 (1->0, 0->1)	~A	0b...11110101 (보수연산)
<< (왼쪽 시프트)	비트들을 왼쪽으로 이동	A << 1	0b10100 (20)
>> (오른쪽 시프트)	비트들을 오른쪽으로 이동	A >> 1	0b0101 (5)

 

---

📌 비트마스킹 활용법 (기본)

 

1️⃣ 특정 원소 추가

bitmask = 0b000 # 초기 상태 (모두 꺼짐)
bitmask |= (1 << 2) # 2번 인덱스(세 번째 자리) 켜기
print(bin(bitmask)) # 0b100 (4)

 

2️⃣ 특정 원소 제거

bitmask = 0b1011  # 현재 상태: 0b1011 (십진수 11)
bitmask &= ~(1 << 1)  # 1번 인덱스(두 번째 자리) 끄기
print(bin(bitmask))  # 0b1001 (9)

 

3️⃣ 특정 원소 토글 (ON <-> OFF 전환)

bitmask = 0b1010  # 0b1010 (십진수 10)
bitmask ^= (1 << 1)  # 1번 인덱스(두 번째 자리) 토글
print(bin(bitmask))  # 0b1000 (8)

 

4️⃣ 특정 원소 확인

bitmask = 0b1010
print(bool(bitmask & (1 << 3)))  # 3번 인덱스에 값이 있는지 확인 (True)
print(bool(bitmask & (1 << 2)))  # 2번 인덱스에 값이 있는지 확인 (False)

---

📌 비트마스킹이 자주 쓰이는 곳

✅ 부분집합 구하기
✅ 집합(Set)처럼 활용하기
✅ 조합(Combination) 구하기
✅ 중복 체크, 방문 체크
✅ 상태 압축 DP