비트마스크 알고리즘/ 집합 구현

BitMask(비트마스크)

비트마스크는 컴퓨터 과학에서 사용되는 개념으로, 비트 연산을 통해 정보를 효율적으로 처리하는 기술입니다.
비트마스크는 이진수로 표현된 비트의 상태를 이용하여 여러 가지 작업을 수행할 수 있습니다. 

특정 비트 위치에 값을 설정하거나 비트를 확인하는 등의 작업이 가능합니다. 비트마스크는 주로 메모리와 연산을 효율적으로 다룰 때 사용되며, 특히 비트 연산자 AND, OR, XOR 등을 활용하여 다양한 연산을 수행합니다.비트마스크는 알고리즘 및 데이터 구조에서 자주 사용되며, 특히 상태나 특정 조건을 효율적으로 표현하고 처리하는 데에 활용됩니다.

 

 

비트 연산자

• AND(&): 두 비트가 모두 1일 때만 결과가 1이 되는 연산. 특정 비트를 0으로 설정하거나 특정 비트를 확인할 때 사용ex) 1 & 1 = 1,  1 & 0 = 0

 

• OR(|): 두 비트 중 하나라도 1이면 결과가 1이 되는 연산. 특정 비트를 1로 설정하거나 특정 비트를 확인할 때 사용    ex) 1 | 1 = 1 , 1 | 0 = 1

 

• XOR(^): 두 비트가 서로 다를 때만 결과가 1이 되는 연산. 특정 비트를 토글하거나 상태를 변경할 때 사용 ex) 1 ^ 1 = 0 , 1 ^ 0 = 1

 

• 비트 왼쪽 시프트 (Left Shift): << 연산자를 사용하여 비트를 왼쪽으로 이동시킴, 이는 주로 값을 2의 거듭제곱만큼 곱하는 효과를 가짐ex) 5 << 2  는 00101 << 2 한 것으로 결과는 10100(20) 이다. 이는 5에 2^2를 곱한 값과 같음
• 비트 오른쪽 시프트 (Right Shift): >> 연산자를 사용하여 비트를 오른쪽으로 이동시킵니다. 이는 주로 값을 2의 거듭제곱만큼 나누는 효과를 가집니다. 예를 들어, x >> y는 x를 y 비트만큼 오른쪽으로 이동시킵니다.
  ex) 12 >> 2  는 01100 >> 2 한 것으로 결과는 00011(3) 이다. 이는 12에 2^2를 나눈 값과 같과 같음

 

 

비트셋(Bitset)

• 비트마스크는 주로 비트셋으로 표현
• 각 비트는 특정 상태를 나타내며, 비트의 위치에 따라 해당 상태가 설정되어 있는지 확인하거나 설정할 수 있음
• ex) 1 -> 존재, 0 -> 존재X로 사용할 수 있음

11111100000111111111111

 

 

 

비트마스크의 활용

• 집합 표현: 비트를 원소의 존재 여부로 사용하여 집합을 효율적으로 표현할 수 있음
• 플래그 조작: 특정 플래그를 설정하거나 확인할 때 사용
• 비트 카운팅: 1로 설정된 비트의 개수를 카운트하여 특정 조건을 확인할 때 활용

 

 

비트마스크를 활용한 집합 표현

집합을 int로 표현한다고 가정

int set = 0;  //{0}

//set에 원소 a 추가
set |= (1 << (a - 1) ) 


//set에 원소 a 삭제
set &= ~(1 << (a - 1))

//set에 원소 상태 확인
int isExist = set & (1 << (a-1))
//0이 아니면 집합에 존재하는 원소임

//1~a까지의 원소 삽입
set = (1 << (a+1)) - 1

//공집합으로 초기화
set = 0