ps를 많이 하시다 보면, 비트 연산자를 써야 하는 경우가 종종 있습니다. 오늘은 c언어에서 어떤 식으로 비트 연산자를 많이 쓰는지 배워보도록 합시다.

 

 


 먼저, 왼쪽 이동과, 오른쪽 이동 연산을 알아야 하는데요. 보통 ps에서는 <<을 많이 씁니다. 좌측으로 비트를 이동시키는 것을. 그러니까 그것만 언급하도록 하겠습니다. 먼저 a = 2라고 해 봅시다.

 

 

 그러면 이런 식으로 bit가 있을 겁니다. 이 때 a = (a<<1);을 해 버리면, 비트들이 왼쪽으로 한 칸씩 이동이 됩니다. 그러면 요런 식으로 될 텐데요.

 

 

 a에 2가 곱해진 것과 같은 효과가 나네요. 1칸을 left shift 하면요. 2칸을 왼쪽 이동 시키면 4가 곱해진 것과 같은 효과가 날 거에요. 다만, 연산의 결과가 범위를 벗어나는 경우에는 조심할 필요가 있어요. 이것은 여기에 이야기를 하기에는 너무 길고, 다음에 이야기를 다시 하도록 하겠습니다.

 

 보통, << 연산자는, 어떠한 수의 비트가 켜져있는지, 꺼져있는지, 그리고 집합에 추가하거나 제거할 때, 기본적으로 쓰이기 때문에 잘 알아둘 필요가 있어요. 연습을 하나 해 봅시다. int형이 4byte라면, 32개의 bit로 구성이 되어 있을 겁니다. 그러면 만약에 a = 1이라면 맨 끝에서 1번째 bit만 켜질 거에요.

 

 

 그러면, 이런 상태일 겁니다. 만약에 맨 끝에서 3번째 비트, 그러니까 2번째 bit만 켜지게 하려면 어떻게 하면 될까요? 4를 곱하면 됩니다. 즉, (1<<2)를 하면 됩니다.

 

 

 여기까지 이해가 되시나요? 그러면 다음으로 넘어가 봅시다.

 

 


 먼저 &와 |를 알아봅시다. 이것은 bit 단위 and인데요. 두 비트가 모두 1이면 1, 그렇지 않다면 0입니다. 예를 하나 들어봅시다. a의 값이 3이고, b의 값이 5입니다. 그러면 a&b의 값은 얼마일까요? 비트로 나타내 봅시다.

 

 

 비트로 나타내면 위 그림과 같이 될 건데요. 두 개의 비트가 모두 1인 bit는 최하위 bit밖에 없어요. 따라서 3&5는 1입니다. 그러면 |는 어떨까요? 이것은 비트 단위로 or를 하는 연산자입니다. 둘 다 0이 아니라면 1입니다. 두 비트 중 최소한 하나의 bit가 1인 경우를 모두 체크해 봅시다.

 

 

 그러면, 0, 1, 2번째 bit이 조건을 만족함을 알 수 있어요. 따라서, 3|5의 값은 7입니다.

 

 


 ~연산자는 비트를 반전시킵니다. 예를 들어 봅시다. a의 값이 5라고 하고, 크기가 1byte라고 해 봅시다. 그러면 a를 bit로 표현하면 다음과 같을 겁니다.

 

 

 이 때 ~a를 하면 bit로 어떻게 표현이 될까요? 간단합니다. 0은 1로, 1은 0으로 반전이 될 겁니다.

 

 

 

 그러면 이렇게 될 겁니다. 크게 어렵지 않네요. 이제 tsp와 같은, 상태 여러개를 정수 하나로 압축하는 방법을 쓸 때, 유용한 몇 가지 트릭을 알려드리도록 하겠습니다.

 

 


 먼저, 집합에 x를 추가하는 연산이 있습니다. 단, x는 자료형이 몇 bit를 가지고 있느냐에 따라서 그 제한이 달라집니다. 만약에 32라면, x는 0이상 31이하이면 되고, 64라면 0이상 63이하이면 될 겁니다. 그런데, x가 추가되지 않은 상태에서 어떠한 연산을 수행한 다음에 추가가 되게 하려면 어떻게 해야 할까요? 2를 추가한다고 해 봅시다.

 

 

 그러면, ?는 일단 1이 되어야 할 겁니다. 그리고 0과 1을 어떠한 연산을 취했는데 1이 나온다. 그러면 후보해가 2개입니다. xor이거나, 아니면 or입니다. 그런데 나머지 ?에 대해서, 이전 상태가 x였다면, 연산을 하고 나서도 x가 되어야 합니다. 이 또한 xor과 or 둘 다 만족을 합니다.

 

 문제는 2번째 bit가 1이 켜진 경우인데요.

 

 

 이 때에는 or인 경우에는 그냥 1을 채우면 됩니다. 1 or 1은 1이기 때문입니다. 하지만 xor이라면 ?가 0이 되어야 합니다. xor로 처리하면 껄끄러워 지는 것이 보입니다. 따라서, 어떠한 상태 a에, 2번째 원소가 있다는 정보를 추가하려면, | 연산자를 써서, a = (a|4); 이렇게 적는 것이 바람직 합니다. 그런데 4는요.

 

 

 1을 왼쪽으로 2번 shift 시킨 값입니다. 따라서, a = (a|(1<<2)); 로 적으면 되겠습니다. 반대로, x를 집합에서 제거하는 연산은 어떻게 하면 좋을까요?

 

 

 1과 ?를 어떠한 연산을 시켰더니 0이 나와야 하는데요. 일단 ?에는 and가 들어가고 0이 들어가거나, 혹은 xor이 들어가고 1이 들어가면 됩니다. 문제는, 이런 경우가 있을 텐데요.

 

 

 이 때, a와 temp를 xor를 시켜서, 3번째 원소를 상태에서 제거하려면, ?에 0이 들어가야 할 겁니다. 복잡합니다. 만약에 and였다면, ?에 0이 들어가면 됩니다. 즉, 어떠한 상태에서 특정 원소를 제거하려면 and를 쓰면 된다는 것을 알았습니다.

 

 

 

 그러면 1과 ?를 and를 했을 때 1이 나오고, 0과 ?를 and 했을 때 0이 나와야 하는데요. 이를 만족하는 ?의 값은 1입니다. 따라서 파란색으로 칠해진 ?에는 1이 들어가야 하겠네요.

 

 

 그런데 이 temp를 보면, 8을, 그러니까 (1<<3)을 ~연산 한 거 같지 않나요? 001000을 bit 반전시킨 겁니다. 따라서, 3번째 원소를 제거하기 위해서, a = (a&(~(1<<3))); 라는 문장을 쓰면 되겠습니다. 정리해 보자면, a라는 state에 x라는 원소가 있다는 정보를 추가하기 위해서, a = (a|(1<<x));를 쓰면 되고, x라는 원소가 있다는 정보를 제거하기 위해서 a = (a&(~(1<<x))를 쓰면 된다는 것입니다.

 

 한 가지 예제를 더 들어봅시다. 만약에 x라는 원소가 있다는 것을 검사하려면 어떻게 하는 것이 좋을까요? 상태가 a라면, a&(1<<x)의 값이 0인지 아닌지 검사하면 됩니다. ? and 1이 0인 경우에 ?의 값은 0이고, ? and 1이 1인 경우 ?의 값이 1이기 때문입니다.

 

 


 조금 더 어려운 예제를 봅시다. 상태를 압축하기 위해서 비트를 이용한다고 했는데요. 하나의 정수에 여러 가지 정보를 담고 있는 경우가 있습니다. 예를 들어서 char형에, 성별, id, 부서 코드 등을 저장할 수 있을 거에요. 물론, 이들을 저장하기 위해서 자료형이 그리 큰 거 같지는 않지만, 예제니까 어느 정도 고려해주시면 좋겠습니다.

 

 

 여기서 g는 성별, b b는 부서 코드, id는 c c c c로 나타낼 수 있어요. 여기서 우리는 부서 코드만 뽑아오려고 합니다. 어떻게 하면 좋을까요? 일단 우리가 가져와야 하는 정보를 빨간 색으로 표시해 봅시다.

 

 

 그러면 우리는 이 값을 가져와야 하는데요. 어떻게 하면 좋을까요? 일단, b는 비트를 2개 차지하고 있습니다. 그렇기 때문에 11이라는 것이 있으면 좋을 건데요. 이는 (1<<2) - 1과 같아요. mask라고 이야기를 많이 합니다.

 

 

 그 다음에, mask를 4만큼 왼쪽으로 shift 시킵니다.

 

 

 x and 1의 값은 x를 만족하기 때문에, a&mask로 값을 끌어오면 v v 0 0 0 0 꼴이 될 겁니다. 이 값을 오른쪽으로 4만큼 shift 시키면 됩니다. 복잡한 듯 싶군요. 간단한 방법이 없을까요? b 오른쪽에 있는 정보가 4비트가 있기 때문에, a를 우측으로 4만큼 이동시키고 mask 값인 3과 and 연산을 하면 됩니다.

 

 

 

 즉 (a>>4)&((1<<2)-1)의 값을 얻어오면 되는 셈입니다. >> 연산자는 unpacking을 할 때 꽤 유용하게 사용이 될 수 있어요. 물론 ps에서 제가 쓴 적은 손에 꼽습니다. <<는 많이 사용했습니다만, >>는 아주 드물게 사용했습니다. 이 두 연산자를 쓸 때 조심해야 하는 것이 몇 가지 있는데요. 그에 대한 내용은 추후에 다시 정리해 드리도록 하겠습니다.