C언어의 기초 - 비트 연산자

*주의 - 개인적으로 학습한 내용이므로 틀린 부분이 있으면 알려주시면 진심으로 감사드리겠습니다.

 

1. 비트 연산자

 

비트 연산자는 이름 그대로 비트 별로 계산을 하겠다는 뜻이다. 

integer type 의 경우 4B를 차지하고 있고, 비트별로 2의 배수를 뜻한다. 

예로 10진수로 24는 2진수로 11000(2) 처럼 각 bit 별로 0 혹은 1로 표시한다.

이걸 bit 별로 0 혹은 1로 바꾸고 싶을 때 쓰는 것이 비트 연산자이다.

 

비트 연산자에는 & ^ | << >> ~ 가 있다.

&과 ^ 과 | 과 ~는 이미 우리가 논리 회로에서 본 적이 있다.

 

&는 and 연산으로 둘 다 1이어야 결과가 1이 나왔었고,

^는 xor 연산으로 비교 대상 둘이 서로 달라야 1이 나왔다.

또한 |는 or 연산으로 둘 중 하나만 1이어도 1이 나왔고,

~는 not 연산으로 0이면 1, 1이면 0 으로 나오는 단항 연산자였다.

 

우리가 모르는 것은 << >> 연산이므로 이걸 먼저 살펴보겠다.

 

<< 연산은 이항 연산자로 좌항을 우항만큼 왼쪽으로 이동시키라는 뜻이다. 

반대로 >> 연산은 좌항을 우항만큼 오른쪽으로 이동시키라는 뜻이다.

 

예를 들어 3 << 1; 의 연산을 할 경우, 3은 2진수로 11이므로 1bit 만큼 왼쪽으로 움직이면 110이 되므로 십진수로는 6이 되게 된다.

만약 3>> 1; 의 연산을 할 경우, 11을 1칸 오른쪽으로 없애야 한다. 이때 영역 밖으로 밀려나면 그 숫자는 사라진다고 가정하기 때문에 1이 연산의 결과로 나오게 된다.

 

여기서 주의해야할 것은 unsigned int 냐 signed int 이냐 이다. 

signed int 의 경우, 31번째 항이 1일 경우 음수를 뜻하는데, 오른쪽으로 미는 비트 연산을 할 경우 31번째 비트에 어떤 숫자가 들어오는지 쉽게 알기 힘들다.

기본적으로 이 경우는 compiler에 따라 다르다. 음수일 경우 항상 31번째 비트를 1로 유지하는 compiler도 있고, 그대로 밀고 0으로 채워버리는 compiler도 있기 때문에 unsigned int 로 써야 안전함을 명심하자. 

unsigned int 의 경우 왼쪽으로 미나 오른쪽으로 미나 항상 0이 채워지기 때문에 항상 예측 가능하다는 장점이 있다.

 

그리고 눈여겨 보면 알겠지만, 왼쪽으로 미는 연산은 한 칸당 2배씩 커진다는 것을 알 수 있다. 

이는 10진수에서 보면 당연한 일인데, 11을 왼쪽으로 한 칸 밀 경우 110이 되므로 10배 커진 것을 알 수 있다.

이를 그대로 2진수에 적용해보면 11을 왼쪽으로 한 칸 밀 경우 110이 되고, 이는 3에서 6이 된 것이므로 2배 커진 것을 알 수 있다. 

그렇기 때문에 최상위 비트인 31번째 비트가 밀려 없어지지 않는 한, << 는 값을 2배씩 한다는 것을 알 수 있고, 반대로 >>는 최하위 비트인 0번째 비트가 밀려 없어지지 않는 한 반으로 작아진다는 것을 알 수 있다.

 

비트 연산은 총 2의 31승 만큼의 경우의수를 4B만에 처리할 수 있어서 메모리 상의 이득을 볼 수 있기 때문에 유용하게 사용한다. 가령 NP문제로 불리는 외판원의 순회 문제 등을 풀 때 유용하게 사용된다. (그래봐야 시간 제한 때문에 못하겠지만)

 

그렇기 때문에 각 비트를 하나의 경우의 수로 보고 각 비트별로 연산할 수 있는 능력이 필요하다.

가령 10번째 비트를 지금 값에 상관없이 항상 1로 만들고 싶으면 어떻게 해야할까?

이럴 경우 | (or) 연산을 써서 해결하면 된다.

0x1 << 10 을 생각해보면, 32비트중 10번째 비트만이 1로 바뀐 상태이고, 이것을 기존의 수와 OR 연산할 경우 10번째 수는 항상 1이 되게 된다.

그러므로 | 연산을 set 연산이라고 부른다.

 

그렇다면 10번째비트를 항상 0으로 만들고 싶다면 어떻게 해야할까?

이럴 경우 &(and) 연산을 활용하면 된다.

and 연산은 그 값이 어떻든 내가 지금 0이라면 항상 0이 나온다.( 1 & 0 = 0, 0 & 0 = 0)

그리고 내가 지금 1이라면 원래 값 그대로 나온다.(1 & 0 = 0 , 1 & 1 = 1)

이 두 경우를 합치면 내가 0으로 만들고 싶은 곳은 0으로 계산하고, 나머지는 1로 계산하면 원래 수에서 원하는 곳만 0으로 바꿀 수 있다.

0x1 << 10 을 한 다음 not 연산을 하면 ~(0x1 << 10) 이 되고, 이는 10번째 비트는 0이고 나머지는 1인 수가 된다.

그리고 이것을 원래 수와 &연산을 하면 10번째 수만 0이 되고 나머지는 유지되는 연산을 할 수 있다.

그러므로 & 연산을 clear 연산이라고 부른다.

 

또 하나 있는데, 그 자리를 지금 갖고 있는 수의 반대값이 되도록 하고 싶을 경우가 있다. 

가령 1이라면 0으로 0이라면 1로 만드는 경우를 뜻한다.

^ (xor) 연산은 이때 쓰인다.

^ 연산은 내가 0이라면 0과 0 = 0, 0과1 = 1 이므로 0을 넣을 경우 결과가 유지되는 것을 알 수 있다.

만약 내가 1이라면 1과0 = 1, 1과 1 = 0 이므로 1을 넣을 경우 결과가 항상 반대가 되는 것을 알 수 있다.

그러므로 0x1<<10 을 한 후 원래 값과 ^ 연산을 할 경우 10번째 수만 반전이 되고 나머지는 유지가 되는 것을 알 수 있다.

그러므로 ^연산을 invert 연산이라고도 한다.

 

그리고 바꾸고 싶은 bit가 여러개의 경우도 쉽게 할 수 있다.

가령 1, 4, 5 번째를 바꾸고 싶다면 1<<1 | 1<<4 | 1<<5 를 하면 1,4,5 번째 수만 1이 되는 수를 만들 수 있고, 그 다음엔 위의 연산과 똑같이 수행하여 바꿀 수 있다. 또한 연속된 수를 바꾸고 싶을 경우 큰 수를 사용해도 된다.

예를 들어 1,4,5일때 4,5는 연속된 숫자이므로 10진수 3을 <<4 연산을 하면 11(2)<<4 의 경우와 동일하기 때문에 두 자리를 한 번에 1로 만들 수 있으므로 코드를 줄이는데 유용하다.

 

이런 bit 연산의 경우 하드웨어를 직접 다루는 영역에서 소중하고 빈번하게 사용되니 잘 외워두는 것이 미래에 도움이 될 것 같다. 추가로 경우의 수도 메모리를 적게 사용할 수 있고 연산 속도도 비트 연산자는 굉장히 빠른 편이니 도움이 될 수 있을 것 같다.