2024 - 10- 18 C++ 코딩테스트 10주완성 D+48

비트마스킹 활용법

 

idx번째 비트끄기	S &= ~(1 << idx)
idx번째 비트 XOR 연산	S ^= ( 1 << idx)
최하위 켜져있는 비트 찾기	idx = (S & -S)
크기가 n인 집합의 모든 비트를 켜기	(1 << n) -1
idx번째 비트를 켜기	S |= ( 1 << idx)
idx번째 비트가 켜져 있는지 확인하기	if(S & (1 << idx))

 

1. idx 번째 비트끄기 ( S &= ~(1 << idx))

 

예시를 들어 S = 10010(18) 이라는 비트가 있다고 하자

이중에서 10010 이 부분의 비트를 끄고 싶다면

1에 해당하는 인덱스를 1 << 1(해당 인덱스번호) 하여 반전하고 싶은 비트만 따로 만들어준다.

그러면 00010 이라는 비트가 만들어진다. 이 비트를 ~ 연산자를 사용하여 뒤집어 준다.

그러면 11101 이라는 비트가 만들어지고 이 비트를 S 와 & 연산자를 하면 10000 이라는 비트가 나온다!

 

 

 2. idx 번째 비트 XOR 연산 ( S ^= ( 1 << idx))

 

예시를 들어 S = 10010(18) 이라는 비트가 있다고 하자

이중에서 10010 이 부분의 비트를 XOR 연산하고 싶다면

1에 해당하는 인덱스를 1 << 1(해당 인덱스번호) 하여 해당인덱스만 따로 빼내어준다.

00010 이라는 비트값이 나올 것이다.

이것을 S 와 ^(XOR) 을 하여주면 10010, 00010 둘다 1이므로 0으로 반환된다!

0일 경우에도 마찬가지다.

마찬가지로 10010를 예로 들고 10010 이 부분의 비트를 XOR 연산하고 싶다면

똑같이 0에 해당하는 인덱스 1 << 2 하여주면 00100 이다.

이를 S 와 ^(XOR) 하여주면 10010 , 00100 하나가 1이므로 1을 반환한다!

따라서 해당 인덱스가 0일떄 1을 반환 1일때 0을 반환시키는 XOR 연산이 된다.

 

3. 최하위 켜져있는 비트 찾기 ( idx = (S & -S))

 

주어진 비트의 오른쪽부터 탐색하여 1인 인덱스를 반환시켜주면 된다.

예시를 들어 10010(18) 이 주어졌다고 치자.

10010을 ~ 연산자를 이용하면

~S = -(S + 1) 이므로 01101 + 1 이다. 따라서 01110 이라는 값이 나온다.

이를 S 랑 & 연산하여주면 10010 & 01110 = 00010 이라는 비트가 나오게 된다!

 

4.크기가 n인 집합의 모든 비트를 켜기 ( (1 << n) - 1)

예를 들어 1 << 4 를하여 10000 이라는 비트가 있다고 하자.

여기다가 -1 연산을 하여주면 01111 이라는 비트가 나온다.

따라서 (1 << n) 을 하여준 뒤 -1 연산을 하여주면 크기가 n인 집합을 모두 켤 수 있다!

 

5.idx 번쨰 비트를 켜기 (S |= (1 << idx))

 

예를 들어 10010(18) 이라는 비트가 있다.

여기서 10010 의 비트를 키고 싶으면, 1 << 3 을 하여주면 01000 이라는 비트가 나온다.

이를 10010 과 | 연산을 쓰게되면 10010 | 01000 = 11010 이라는 수가 나오게 된다.

그냥 단순하게 해당 인덱스를 1로 만들고 OR 연산자를 이용하여 합쳐주는 것이다!

 

6.idx 번째 비트가 켜져있는지 확인하기 ( if(S & (1 << idx)))

 

만약 10010 이라는 이진수가 있고, 3번째 비트가 켜져있는지 확인하고 싶다고 가정하자!

먼저 1 << 3 을 하여 00100 을 만들어준다.

그 다음 10010이랑 & 연산을 하면 10010 & 00100 = 0 둘중 하나가 0이여서 0이 반환됐다.

이렇게 idx 번째 비트만 가져와 & 연산을 하여주면 0이면 0이 반환 1이면 1이 반환된다!