[Algorithm] 비트마스킹

✅ 비트 마스킹

기본 지식

• 컴퓨터는 모든 정수형 변수를 이진수로 표현함

• 예를들어 6비트를 사용해 0~63 까지 표현할 수 있다

  • 0 = 000000
  • 63 = 111111

• 부호 없는 N 비트 정수형의 경우

  • 2^0 을 최하위 비트 (Least significant bit)
  • 2^(N-1) 을 최상위 비트 (Most significant bit)

 

 

✅ 비트연산자

모든 자릿수가 비트 (0 또는 1)로 이루어진 값에 대하여 아래의 연산이 가능함

비트가 1이면 켜져있음 , 0이면 꺼져있음

 

• AND 연산 a & b
• OR 연산 a | b
• XOR 연산 a ^ b
• NOT 연산 ~a

• LEFT SHIFT 연산 a << b
• RIGHT SHIFT 연산 a >> b

 

 

✅ 피자 가게 예제

10자리 비트(0~9)의 각 자릿수가 피자의 서로 다른 토핑의 첨가 유무

10자리 비트 값으로 피자를 나타내는 상황

 

# 공집합과 꽉찬 집합의 경우

• 토핑이 없는 피자

  • int emptyPizza = 0

• 모든 토핑이 들어간 피자

  • int fullPizza = (1<<10) -1

 

# 원소 추가

• 피자에 n번 토핑 추가하기

  • pizza |= (1<<n)

 

# 원소 포함여부 확인

• 피자에 n번 토핑이 들어있는지 확인하기

  • if( pizza & (1<<n) ) cout << "Found!" << "\n"
  • 값이 들어있으면 (1<<n) 리턴
  • 값이 들어있지 않으면 0 리턴

 

# 원소 삭제

• 피자에 n번 토핑 빼기

  • pizza &= ~(1<<n)

 

# 원소 토글

• 피자에서 n번 토핑이 들어가있으면 빼고, 없으면 추가함

  • pizza ^= (1<<n)