PS용 비트 연산자(bit masking) 정리

내가 보려고 정리

 이 내용은 신촌 연합 알고리즘 캠프 강사님 말씀이다.

- 집합 관리

{0,1,2,3,4,5} 에서 부분집합 {0,1,4} 를 비트로 관리할 때 -> 0 1 0 0 1 1 로 관리 (5,4,3,2,1,0) 순서로 있으면 1, 없으면 0 

교집합 -> & 연산자, 합집합 -> | 연산자 사용

 

-i 번째 비트 구하기 

1. x & (1 << i) 

ex) 0 1 0 1 1 에서 3번째 비트를 구하려면 0 1 0 0 0 과 & 연산자를 취해주면 됨. 단, 이 때는 결과가 0이면 i번째가 0이고 0이 아니면 i번째가 1이구나로 판단

 

2. (x >> i) & 1

ex) 같은 예제에서 0 1 0 1 1 을 3만큼 right shift 해준 값과 & 연산을 취하면, 0 0 0 0 1 즉, 1과 & 연산을 취하게 된다.

그럼 전체 결과가 1인지 0인지로 판단 가능하다.

 

- i번째 비트를 0/1로 설정하기

1. 1로 설정하기  x | (1 << i)

x | (1 << i), 해당 자리에 1과 OR 연산 취해주면 1로 바뀌는 것 이용

만약 원래 그 자리가 0 인걸 알고 있다면 x + (1 << i) 를 사용해도 된다.

 

2. 0으로 설정하기 x & ~(1 << i)

ex) 0 1 0 1 1 에서 3번째를 0으로 바꾸고 싶을 때, 1 0 1 1 1 즉, 해당자리에 0을 주고 & 연산을 취하면 0으로 바뀌게 된다. 그러면 1 0 1 1 1 을 어떻게 찾느냐

-> 해당 자리만 1로 만든 0 1 0 0 0 에서 ~(NOT) 연산을 취한 값이다. 

즉,  x & ~(1 << i)

만약 원래 그 자리가 1인걸 알고 있다면, x - (1 << i) 로 사용할 수 있다.

 

- 마지막 n 비트 구하기 

x & ((1 << n) - 1)

ex) 0 1 0 1 1 에서 마지막 3 비트를 구하고 싶다면 0 0 1 1 1 과 &를 취해주면 된다. 

0 0 1 1 1 은 무엇이냐? 

-> 0 1 0 0 0 에서 1을 뺀 값이다.

따라서, x & ((1 << n) - 1) 

 

- i번째 비트 반전

x ^ (1 << i)

ex) 0 1 0 1 1 에서 3번째 1을 0으로 바꾸고 싶다면 0 1 0 0 0 과 XOR 연산을 취해주면 된다.