C 의 비트연산자에 대한 흥미로운 사실들

저의 글은 geeksforgeeks 의 글을 참조해 작성했습니다. 

---

C 에는 6가지의 비트 연산자가 있습니다. 

& (bitwise AND) : 2개의 숫자의 이용해 각 숫자들의 모든 비트의 AND 연산을 수행합니다.
양쪽 비트가 모두 1이면 1을 출력합니다. 그 외에는 0.

| (bitwise OR) : 2개의 숫자의 이용해 각 숫자들의 모든 비트의 OR 연산을 수행합니다.
두개의 비트들중 하나가 1이라면 1을 출력합니다. 그 외에는 0.

^ (bitwise XOR) : 2개의 숫자의 이용해 각 숫자들의 모든 비트의 XOR연산을 수행합니다.
양쪽 비트가 다르면 (1,0 또는 0,1), 1을 출력합니다. 그 외에는 0.

<< (left shift) : 2개의 숫자를 입력받아 비트들을 왼쪽으로 옮깁니다. 

>> (right shift) : 2개의 숫자를 입력받아 비트들을 오른쪽으로 옮깁니다. 

~ (NOT) : 한 숫자에 대한 모든 비트들을 거꾸로 합니다. (0 -> 1 또는 1 -> 0)

비트 연산자에 대한 예시 코드가 있습니다.

/* C Program to demonstrate use of bitwise operators */
#include<stdio.h>
int main()
{
    unsigned char a = 5, b = 9; // a = 5(00000101), b = 9(00001001)
    printf("a = %d, b = %d\n", a, b);
    printf("a&b = %d\n", a&b); // 결과값은 is 00000001
    printf("a|b = %d\n", a|b);  // 결과값은 is 00001101
    printf("a^b = %d\n", a^b); // 결과값은 is 00001100
    printf("~a = %d\n", a = ~a);   // 결과값은 is 11111010
    printf("b<<1 = %d\n", b<<1);  // 결과값은 is 00010010 
    printf("b>>1 = %d\n", b>>1);  // 결과값은 is 00000100 
    return 0;
}

출력값 : 

a = 5, b = 9
a&b = 1
a|b = 13
a^b = 12
~a = 250
b1 = 4

이제 비트연산자에 대한 소개가 끝냈으니, 흥미로운 사실들을 말씀드리겠습니다.

1) left shift 연산자와 right shift 연산자는 음수에는 사용되지 않도록 해야 합니다.

두개의 숫자중 하나라도 음수라면 연산의 결과는 정의되지 않은 행동(undefined behavior) 가 되어버립니다. 
예를 들어 -1 << 1 과 1 << -1 의 결과값은 정의되지 않습니다. 
또한 숫자를 shift 했을때 정수(integer) 형의 크기를 넘겨버리는 상황이 발생한다면, 이 역시 정의되지 않습니다.
예를 들어, 1 << 33 의 값을 32 비트의 정수형 변수에 저장하려 한다면 정의되지 않습니다.  

2) XOR 연산자는 기술 면접에서 굉장히 유용한 연산자로 쓰입니다.

많은 문제들에서 XOR 연산자를 사용하죠. 가장 간단한 예를 들자면 "단 하나의 숫자만 제외하고 모든 숫자들이 짝수번 만큼 들어있는 숫자들의 집합에서 홀수번 만큼 들어있는 숫자를 찾아라" 라는 문제에서, XOR 연산자를 모든 숫자에게 대입한다면 쉽게 구해질 수 있습니다.

// 홀수번 만큼 발생한 숫자를 찾아내는 함수
int findOdd(int arr[], int n) {
   int res = 0, i;
   for (i = 0; i < n; i++)
     res ^= arr[i];
   return res;
}
 
int main(void) {
   int arr[] = {12, 12, 14, 90, 14, 14, 14};
   int n = sizeof(arr)/sizeof(arr[0]);
   printf ("The odd occurring element is %d ", findOdd(arr, n));
   return 0;
}
// Output: 홀수번 만큼 들어있는 숫자는 90 입니다.
 

어떻게 찾을 수 있는걸까요? 

같은 숫자를 XOR 연산하게되면 0 이 나옵니다. ( 90^90 = 0 ) 그리고
0 에 어떤 숫자든 XOR 연산을 하면 그 숫자가 그대로 나옵니다. ( 0^90 = 90 ) 
그렇기에, 주어진 배열에 있는 모든 숫자를 XOR 연산하게 된다면 짝수번 XOR 연산은 모두 0 으로 사라질것이고,
홀수번째의 숫자만 살아남을 것이기에 쉽게 찾을 수 있게됩니다. 
위의 코드 예제에서는,

res = 0 (초기설정) , 0^12^12 = 0 그리고 14^14^14^14 = 0 마지막으로, 0^90 = 90 , 즉, res = 90

이런식으로 계산이 됩니다.

3) 비트 연산자는 논리 연산자로는 사용할 수 없습니다.

논리 연산자들 (&&, || 그리고 !) 의 결과값은 0 또는 1이 됩니다. 하지만 비트연산자의 결과값은 정수값이죠. 
또한 논리연산자들은 0 이 아닌 피연산자를 1로 생각합니다.
예를 들어 아래와 같은 & 와 &&를 구분하기 위한 프로그램을 생각해보세요.

int main()
{
   int x = 2, y = 5;
   (x & y)? printf("True ") : printf("False ");
   (x && y)? printf("True ") : printf("False ");
   return 0;
}
// Output: False True

2 는 2진수로 0010 이고 5는 2진수로 0101 입니다. 둘의 비트 AND 연산 값은 0000 즉 False 죠.
하지만 논리연산자는 x,y 가 모두 0 이 아니므로 True 값인 1로 보기때문에, 1 && 1 = 1 이므로 True 를 출력하게 됩니다.

4) left shift 연산자와 right shift 연산자는 각각 2를 곱한것과 나눈것으로 생각해도 괜찮습니다.

1) 에서 언급한바와 같이, 이는 오직 양수에서만 적용되는 얘기 입니다.

int main()
{
   int x = 19;
   printf ("x << 1 = %d\n", x << 1);
   printf ("x >> 1 = %d\n", x >> 1);
   return 0;
}
// Output: 38 9

5) & 연산자는 숫자가 짝수인지 홀수인지 굉장히 빠르게 체크할 수 있게 도와줍니다.

x & 1 값은 x 가 홀수면 0 이 아닌 값을 출력하고 짝수라면 0 을 출력합니다. 

int main()
{
   int x = 19;
   (x & 1)? printf("Odd"): printf("Even");
   return 0;
}
// Output: Odd

19 는 10011 이고 1 은 00001 입니다. 둘의 AND 비트 연산 값은 00001 이죠. 즉 1 이므로 홀수라는 값이 출력됩니다.

6) ~ 연산자를 주의깊게 사용하세요

부호가 없는 변수 (unsigned variable) 에 어떤 값을 저장하고 그 변수의 ~ 비트 연산을 취하면 작은 값이라도 큰 값이 나오게 할 수 있습니다. 그리고 부호가 있는 변수 (signed variable) 이라면 음수의 값이 나올 수도 있습니다. ( 가장 왼쪽의 비트값이 부호비트인 2의 보수로 음수가 표현된다는 전제하에 말이죠)

// 아래 프로그램은 컴파일러에 따라서 출력값이 달라질 수 있습니다.
int main()
{
   unsigned int x = 1;
   printf("Signed Result %d \n", ~x);
   printf("Unsigned Result %ud \n", ~x);
   return 0;
}
/* 출력값: 
Signed Result -2 
Unsigned Result 4294967294d */

---

위와 같은 비트 연산의 흥미로운 사실들을 이용해서 프로그래밍 문제를 푸는데 이용해 보는 글을 올리겠습니다 ~