c언어 xor 연산자 ^ 에 대해 간단히 알아봅시다.

 안녕하세요. 이번 시간에는 비트 연산자 중에서 요새 자주 써 먹는 것 중 하나인 xor 연산자를 보겠습니다. bit dp를 푸실 때도 나름 유용하게 쓰일 수 있는 것이니 잘 알아가시면 좋겠습니다.

 

---

 먼저 bitprint 함수를 소개하겠습니다. int형 변수 x가 들어오면, 이것의 비트를 출력해 줍니다.

 

 예를 들어 15는 00000000 00000000 00000000 00001111 이렇게 나타날 겁니다.

 

 

 보통 비트는 집합과도 잘 쓰이는데요. 예를 들자면 tsp 문제에서 어떤 도시를 방문했는가와 그렇지 않았는가는 0이나 1로 표현이 될 겁니다. 그러니 비트로 나타내면 좋을 거에요. 1번째 도시를 방문했다면 1, 아니면 0. 이렇게요. 여기서 사용되는 것도 집합입니다. 방문한 도시의 집합.

 

 그런데, 집합 S에서 i를 제거하는 연산을 저는 11번째 줄과 같이 수행했어요. (1<<2)는 00000000 00000000 00000000 00000100입니다. ~는 비트 반전이므로 11111111 11111111 11111111 11111011이 될 겁니다. 기존 state에서 2번째 비트만 0인 것을 and 하게 되면, 2번째 비트가 1인 경우에, 2번째 비트가 0이 될 겁니다. 이를 이용해서, 11번째 줄은 집합에서 2를 제거하게 됩니다. 그런데, 2가 집합에 있다면, 조금 더 간결한 표현으로 제거할 수 있습니다.

 

 

---

 xor은 비트 값 a와 b가 있을 때 a와 b의 값이 같으면 0, 다르면 1이 됩니다.

 

 

 그래서, 11과 3을 xor 하면 아래와 같이 됩니다.

 

 비트가 다른 부분만 1이 되기 때문에, 11 xor 3은 8이 됩니다. 그러면, 이것을 어떻게 비트로 표현된 집합에서 2번째 요소를 제거하는 연산에 응용할 수 있을까요? 

 

 위에 있는 표를 보면, bit1이 켜진 경우를 군청색으로 표시해 봤어요. 그리고 bit2와 xor 연산을 했을 때 ret가 꺼지는 경우에, bit2를 노란색으로 표시해 봤는데요. bit2가 1일 때 꺼지는 것을 볼 수 있어요. 만약에 특정 bit가 켜져 있다면 끄기만 하면 되므로, 특정 비트만 1이 되면 됩니다. 만약에 2번째 비트가 켜진 수에서 2번째 비트만 끄려고 한다면, 2번째 비트만 1인 수와 xor를 하면 됩니다. 2번째 비트만 1인 수는 (1<<2)입니다.

 

 

 따라서, state와 (1<<2)를 xor 연산하면 됩니다. 15는 0, 1, 2, 3번째 비트가 켜져 있는 수인데요. (1<<2)와 xor한 결과를 보겠습니다.

 

 

 그러면 집합에서 2번만 제거되었음을 알 수 있어요. 사실 켜진 비트여야지만 하는 것이 함정이지만요.

 

 

---

 그러면, bit dp에서는 어떻게 응용할 수 있을까요? tsp 문제에서 재귀적으로 구현하게 된다면, cur_state 중에 켜진 비트를 하나 꺼서 재귀 호출을 하게 됩니다. 이 켜진 비트들을 검출하기 위해서, for loop를 돌리게 됩니다. 여기서 중요한 것은 '켜진 비트'를 끈다는 것입니다.

 

 

 그러면 위와 같이 작성하셔도 됩니다. s번째 비트가 꺼진 비트인지는 14번째 줄에서 검사하게 됩니다. 만약에 꺼졌다면, if문이 성립해서 15번째 줄인 continue 문을 수행할 거에요. 그렇지 않으면, 0 ~ 3번째 bit가 켜진 15하고 s번째 bit만 켜진 수하고 xor을 할 겁니다. 이제, bitprint가 어떤 state에 대해서 출력하는지만 보면 됩니다.

 

 

 정확하게 00000000 00000000 00000000 00001111에서 하나의 비트만 꺼진 수만 출력했음을 알 수 있습니다.