[C언어] 비트연산

비트연산을 쓰는 이유에 대하여

비트연산은 여러분야에서 활용도가 높다. 컴퓨팅 시스템에서 오류검출, 네트워크 시스템에서의 오류검출, 그리고 알고리즘에서의 상태저장 등등에 쓰인다.

 

그중 알고리즘측면에서 비트연산은 N개의 지점에 대해 0과1로 그 상태를 저장해둘때 유용하다.

 

예를들어 N개의 도시를 한번씩 방문하면서 순회하는 외판원 문제에서 각 도시들의 방문상태를 저장할때

 

일반적인 배열을 사용하게 되면 N만큼의 int를 사용하게 되고 N * 4byte의 공간을 사용하게 된다.

 

그러나 N이 15라고 가정할때 배열에서는 15 * 4byte = 60 byte를 사용하게 되는데 

비트연산에서는 2^15 = 32768 이므로 1개의 int(약 -21억~21억)내에 들어오게되므로 4byte에 처리가 가능하다.

 

이렇게 보면 별 차이가 없어보이지만

 

외판원처럼 순회하면서 이 도시들의 방문상태를 저장해두고 dp를 이용해야할때 큰 차이가 생긴다.

 

---

비트연산 사용법

비트연산에 대해 알아보기 전에 2진수에 대해서 살펴보자.

 

 

다음과 같이 10진수들을 2진수로 변환할수 있고 2진수에서 1과 0을 통해 외판원 문제의 경우 1은 방문한도시, 0은 아직 방문하지 않은 도시로 값을 저장할수 있다.

 

예를 들어 7개의 도시가 있고 1번째,5번째 도시를 방문한 상태면 

 

위의 4번째 예제처럼 1000100 으로 표시할수 있고 실제 저장되는 값은 68이다.

 

논리 연산자 &  |  ^

& : AND

| : OR

^ : XOR

을 의미한다.

 

n = 85, m = 35 일때 각각의 연산의 실행결과이다.

 

 

시프트 연산자 << >>

<< >> 기호는 현재 비트를 해당 방향으로 시프트하는 것을 의미한다.

 

n = 87일때 

n << 3 과 n >> 2 의 실행결과는 다음과 같다.

 

위 실행결과의 n >> 2를 보면 알수 있듯 우측으로 밀려서 짤린 값들은 그대로 사라진다. 다시 n << 2한다고 그 전값이 나오지 않는다.

 

또한 << 연산으로 int 범위를 초과하지 않게 주의할 필요가있다.

 

이를 이용해 위의 실행결과를 출력시킬때 사용한 함수를 만들어보자

 

이 함수는 정수를 입력했을때 위의 결과처럼 2진수로 표현해주는 함수이다.

 

int bit(int n){
    int i = 0;
    printf("0");
    for(i=30;i>=0;i--){
        if((1<<i) <= n && n > 0){
            printf("1");
            n = n - (1<<i);
        }
        else{
            printf("0");
        }
        if(i%4 == 0){
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}