[C++] 비트 연산

※ int는 32bit (4byte)이지만, 이 게시물에서 편의상 8bit로 표현하였음

비트 연산자

	a = 0b1110 / b = 0b0100		활용
& (AND)	a & b = 0b0100	둘 다 1이면 켜짐	어떤 비트가 켜져 있는지 확인
| (OR)	a | b = 0b1110	둘 중 1이 하나라도 있으면 켜짐	비트를 켤 때
^ (XOR)	a ^ b = 0b1010	서로 다르면 켜짐	비트를 끄거나 반전시킬 때
~ (NOT)	~a = 0b0001	비트를 반전시킴	비트를 끌 때 (&와 함께 사용)
<< (왼쪽 Shift)	a << n = a * (2 ^ n)
>> (오른쪽 Shift)	a >> n = a * (2 ^ -n)

 

비트 연산을 사용할 때 우선순위에 주의가 필요하다. 일반적으로 사칙연산(+, -, *, /)은 비교, 논리 연산자(==, >, && 등)보다 우선순위가 높다.하지만 비트 연산은 논리 연산보다 우선순위가 높으나 비교 연산보다 낮다.

 

따라서 비트 연산자를 쓸 때 꼭 괄호를 쓰도록 하자!!

if(x & y == 0)   // if(x & (y == 0)) 과 같음
if((x & y) == 0)  // 괄호 쓰기!!

& (AND)

3번 비트가 켜져있는지 확인하려면? 00001000과 AND 한다.

00001010 & 00001000 -> 00001000

결과값 비트에서 3번 비트가 1이므로 원본 비트의 3번 비트가 켜져있는 것이다.

 

00000010 & 00001000 -> 00000000

3번 비트가 꺼져있다면 결과값 비트에서 3번 비트가 0으로 나온다.

 

 

AND 연산은 다음과 같이 조건문에서 비트가 켜져 있는지 확인할 때 주로 사용한다.

int x = 10;  // 00001010
// 1 << 3    // 00001000

if(x & (1 << 3) != 0) {  // 3번 비트가 켜져 있는지 확인
}

| (OR)

3번 비트를 켜려면? 00001000과 OR 한다.

01100010 & 00001000 -> 01101010

 

 

OR 연산은 비트를 켤 때 사용한다.

int x = 98;  // 01100010
// 1 << 3    // 00001000

x |= (1 << 3);  // 106 (01101010)

^ (XOR)

3번 비트를 반전시키려면? 00001000과 XOR한다.

00001010 ^ 00001000 -> 00000010

원본 비트의 3번 비트가 켜져 있었을 때, 반전시켜서 3번 비트가 꺼진다.

 

00000010 ^ 00001000 -> 00001010

원본 비트의 3번 비트가 꺼져 있었을 때, 반전시켜서 3번 비트가 켜진다.

 

 

XOR 연산은 비트를 켜져있으면 끄고, 꺼져있으면 켤 때 사용한다.

비트가 켜져있는지 꺼져있는지 확인하기 위해 조건문, AND을 함께 사용할 수 있다.

int x = 10;  // 00001010
// 1 << 3    // 00001000

if(x & (1 << 3) != 0){   // 3번 비트가 켜져 있으면
	x ^= (1 << 3);   // 3번 비트 끄기 : 2 (00000010)
}

 

 

또한, 다음과 같은 XOR의 특징은 많은 문제에 적용할 수 있다.

- 같은 비트를 XOR하면 0이 됨    3 ^ 3 = 0

- 0을 XOR하면 그대로    3 ^ 0 = 3

 

문제 1) 다음 중 홀수 개 있는 수는?

3 3 3 3 6 6 7 7 7

-> 전체를 XOR하면 된다.

같은 수를 XOR했을 때, 짝수 개이면 0이 되고 홀수 개이면 n이 된다.

 

문제 2) 각 변이 x축 또는 y축에 평행한 직사각형이 있다. 세 꼭지점의 좌표가 주어졌을 때 남은 한 꼭지점의 좌표를 어떻게 구할 수 있을까?

-> (x0 ^ x1 ^ x2, y0 ^ y1 ^ y2)

~ (NOT)

NOT은 AND연산자와 함께 비트를 끄는 데 사용될 수 있다.

int x = 10;  // 00001010
// 1 << 3    // 00001000

x &= ~(1 << 3);  // 2 (00000010)

>>, << (SHIFT)

정수 자료형을 왼쪽으로 i칸 밀거나 오른쪽으로 i칸 미는 연산은 각각 2^i를 곱하거나 2^i로 나누는 연산과 같다. 특히 / 연산은 느리므로 나누는 수가 2의 거듭제곱일 경우 >>로 바꾸어 성능을 향상시킬 수 있다.

---

데이터 압축

문자열 두 개를 비교하는 데는 O(문자열의 길이)의 시간이 든다. 사용하는 문자의 가지수가 적다면 필요한 bit만 골라내서 정수형 자료형에 압축할 수 있다.

 

예를 들어, 문자열이 알파벳 대문자로만 이루어졌다면 알파벳끼리 구분하는 데에 1 이상 26 이하의 값만 필요하다. 이는 5bit(26이 11010이므로)만으로 표현할 수 있다.

// 12자 이내의 알파벳 대문자 문자열을 하나의 long long 변수에 압축
long long compress(char str[13]){
    long long res = 0;
    for(size_t i = 0; i < 12; i++){
    	res = (res << 5) | (str[i] ^ 64);
    }
    return res;
}