비트마스킹(BitMasking)

비트마스킹(BitMasking)이란?

• 비트마스킹이랑 비트 연산에 사용되는 데이터 형태로, 개별 비트를 on/off 상태인 1, 0으로 표현한다.
• 1, 0으로 존재 여부, 선택 여부를 나타내고 이진 연산을 수행하는 데에 빠른 연산을 지원한다.
• 단, 너무 큰 수는 이진수로 나타내는 데에 한계가 있다.
• 비트마스킹은 또한 전체 집합의 일부 요소를 선택해 만든 부분집합을 표현하는 데에도 빠르고 메모리 효율적이다.
  해당 원소가 존재하면 1, 그렇지 않으면 0으로 표현할 수 있다.

 

비트 연산자 

연산자	동작	a = 0011, b = 0110
&	AND 연산, 두 비트가 모두 1일때 1	a&b = 0010
|	OR 연산, 두 비트 중 하나라도 1일때 1	a|b = 0111
^	XOR 연산, 두 비트 중 하나만 1이고 나머지는 0일때 1	a^b = 0101
~	NOT 연산, 1이면 0, 0이면 1	~a = 1100
<<	왼쪽 시프트, 지정된 비트 수만큼 왼쪽으로 이동	a<<2 = 1100 1<<4 = 10000 1<<0 = 1
>>	오른쪽 시프트, 지정된 비트 수만큼 오른쪽으로 이동	b>>1 = 0011

원소 추가 

a |= (1<<n) : n자리 비트만 1로 바꾼 수와 a와 or 연산을 통해 n번째 원소 추가 

ex. a = 1000 , n = 2

      (1<<2) = 100

      a |= 100 = 1100

 

원소 삭제 

a &= ~(1<<n): n번 비트를 0으로 만든 수와 AND연산 수행해서 n번 비트 0으로 바꿈 

 

원소 토글 

a ^= (1<<n): XOR 연산을 이용해 n번 비트가 존재하면 0, 존재하지 않으면 1로 변환 

 

n번째 원소 포함여부 확인 

if a & (1<<n): AND 연산을 이용해 n번째 비트가 존재하면 True 존재하지 않으면 False 

 

집합연산 

a|b : 합집합 리턴 

a&b: 교집합 리턴 

a&~b: a-b 차집합 리턴 

a^b : a, b 둘 중 하나의 집합에만 포함된 원소들의 집합 

 

부분집합의 원소의 갯수 

2진수로 변환하면서, 1의 갯수 더해주기 

def count(n):
  if n == 0: return 0 
  return n%2 + count(n//2)