[알고리즘 이론] 비트 연산 - BitMask

비트 연산

연산자	연산자의 기능	비트 마스킹에서 사용 경우
&	비트 곱; 비트 단위로 AND연산을 한다.	비트 flag를 확인할 때
|	비트 합; 비트 단위로 OR연산을 한다.	비트 flag를 set할 때
^	배타적 논리합; 같으면 0, 다르면 1
~	역; 단항 연산자로 비트를 반전시킨다.
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다. (이동 후 남은 오른쪽 자리는 0으로 채움)	1을 shift하는 것으로, 비트 1자리를 flag 역할로 사용할 수 있음
>>	피연산자의 비트 열을 오른족으로 이동시킨다. (이동 후 남은 왼쪽 자리는 비트 부호로 채움)
>>>	자바에만 있는 연산자로 >> 와 같지만, 이동 후 남은 왼쪽 자리는 0으로 채움

비트의 가장 왼쪽 비트는 부호비트이다.

📌 비트 마스크

• 알고리즘의 테크닉 중 하나로, 정수의 이진수 표현을 활용한 기법으로 아래와 같은 특성을 활용

1. 비트는 0 / 1을 가진다 -> ture / false로 표현 가능
2. 이진수는 십진수로 표현 가능 즉, 비트 하나 당 flag 1개의 역할을 할 수 있다.
   
   

비트 연산자로 비트 마스킹 사용하기 - Bit Flag

• 우선 순위 : 시프트 연산자 > 비트단위의 논리 연산자
  int flag : 인트형으로 32bit flag를 세울 수 있다.
  n : 시프트 할 횟수 : $2^n$

1. flag 확인 - flag & 1<<n
2. flag set - flag | 1<<n
   
   

바이너리 카운팅

Binary Counting

• 원소 수에 해당하는 N개의 비트 열을 이용
• n번째 비트 값이 1이면 n번재 원소가 포함되었음을 의미

  예제

  집합 {0,1,2,3}가 있을 때, 이 집합의 부분집합을 구하려면 비트 마스크를 사용할 수 있다.

  이진수	십진수	뽑은 자리	뽑은 원소
  0000	0	뽑은 자리 없음	공집합 {}
  0001	1	4	{3}
  0010	2	3	{2}
  0011	3	3,4	{2,3}
  0100	4	2	{1,}
  0101	5	2,4	{1,3}
  0110	6	2,3	{1,2}
  0111	7	2,3,4	{1,2,3}
  1000	8	1	{0}
  1001	9	1,4	{0,3}
  1010	10	1,3	{0,2}
  1011	11	1,3,4	{0,2,3}
  1100	12	1,2	{0,1}
  1101	13	1,2,4	{0,1,3}
  1110	14	1,2,3	{0,1,2}
  1111	15	1,2,3,4	{0,1,2,3}