[WEEK01] 비트마스킹

비트마스킹(Bitmasking)란?

비트마스킹(Bitmasking)은 정수를 이진수(Binary)로 표현하여, 비트 단위 연산을 통해 데이터를 효율적으로 처리하는 기법이다. 주로 부분 집합 문제, 최적화 문제, 플래그(Flag) 관리 등에 사용된다. 특히 CPU나 메모리의 크기가 작은 임베디드 시스템 및 OS의 경우에서 유용하게 사용된다.

비트 연산자

비트마스킹에서 사용되는 주요 연산자는 다음과 같다.

연산자	설명
& (AND)	두 비트가 모두 1일 때만 1
` (OR)	하나라도 1이면 1
^ (XOR)	서로 다른 경우 1, 같으면 0
~ (NOT)	비트를 반전
<< (Left Shift)	비트를 왼쪽으로 이동 (2배 증가)
>> (Right Shift)	비트를 오른쪽으로 이동 (1/2배 감소)

비트마스킹 활용 예제

특정 비트 확인하기

(num & (1 << i)) != 0   # num의 i번째 비트가 1인지 확인

특정 비트 켜기 (1로 만들기)

num |= (1 << i)

특정 비트 끄기 (0으로 만들기)

num &= ~(1 << i)

특정 비트 토글 (반전)

num ^= (1 << i)

비트마스킹 활용 사례

• 부분 집합 구하기
• 중복 없는 상태 관리 (예: 방문 체크)

정리

비트마스킹은 효율적인 연산을 위해 알고리즘 문제에서 자주 활용되는 기법이다. 특히 부분 집합 생성, 상태 관리, 최적화 문제 등에서 강력한 도구가 될 수 있다. 기본적인 연산을 익히고 다양한 문제에 적용해보면 도움이 될 것이다.