22-01-10 학습일지 [비트 마스크]

비트 마스크 (Bitmask)

- 0 부터 N - 1 까지 정수로 이루어진 집합을 나타낼 때 사용

- 공간을 매우 절약할 수 있음

- 각종 연산을 조금 변형해서 사용해야 함

- 집합 값의 검사, 추가, 제거의 모든 복잡도가 O(1)임

 

A << B -> 비트를 왼쪽으로 한 칸 씩 미는 작업으로, A * 2^B과 같은 뜻

A >> B -> 비트를 오른쪽으로 한 칸 씩 미는 작업으로, A / 2^B과 같은 뜻

 

집합의 값을 검사, 추가, 제거 할 수 있음.

 

비트마스크 S에 X가 있는지 검사 ( AND 연산 )

- S & (1 << X) == 0 이면 없음, 0이 아니면(1<<X)이면 있음

 

비트마스크 S에 X를 추가 (OR 연산)

- 이미 있는 수를 또 추가할 때는 무시. (1 OR 1 = 1이기 때문)

-  S | (1 << X) 하는 것

 

비트 마스크 S에 X를 제거

- AND 연산일 경우 지우려는 값만 0으로 대조시키면 무조건 0으로

- S & ~(1 << X)

 

토글 연산

- 0 < - > 1 SWAP 연산

- S ^ (1 << X)

 

전체 집합

- (1 << N) - 1

 

공집합

- 0

 

비트 연산의 연산자 우선 순위를 잘 생각해야 한다.

- 비트 연산은 사칙연산보다 후순위 연산 순위를 가진다.