1일 1커밋 !

실제 컴퓨팅 작업은 모두 비트단위로 이루어진다. 따라서 동일한 연산을 사용자가 직접 비트 연산을 통해 진행하면 더 좋은 성능을 얻을 수 있다.

비트연산자

비트 연산자에는 총 6 가지를 기억하면 된다.

비트연산자 .. a = 1010, b = 0100
& AND a & b = 0b0000
| OR a | b = 0b1110
^ XOR a ^ b = 0b1110
~ NOT ~a = 0b0101
« 왼쪽 Shift a « n = a * 2^n
» 오른쪽 Shift a » n = a * 2^(-n)

비트 연산자들은 사칙연산들보다 우선순위가 높지만 비교 연산보다 낮음에 주의해야한다!

if (a & b == 0) //if(a & ( b==0 )) 과 같다.

활용 방법

이제 비트 연산자들을 실제로 어떻게 사용할 수 있는 지 알아보자

^ XOR

XOR 을 사용하면 어떤 수에서 몇 개의 비트를 바꿔 대응하는 수를 구할 수 있다. 예를 들어 a ^ 32 를 통해 대소문자를 바꿀 수 있다. 32 = 0B100000 이므로 a에 32에 해당하는 비트가 켜져있으면 끄고 꺼져있으면 킬 수 있다. 이는 대문자를 소문자, 소문자를 대문자로 바꾸는 것과 같은 말이다.

같은 값끼리 XOR 하면 0이 되는 특징을 통해 직사각형의 세 꼭지점을 통해 나머지 꼭지점을 나타낼 수도 있다. 같은 값은 0이 되고 0과 XOR 하면 자기자신이기 때문이다.

~ NOT

NOT 을 사용하면 비트 마스킹 시에서 가지고 있지 않은 원소를 쉽게 구할 수 있다. (아래 참조)

«, » shift

2의 거듭제곱 곱셈이나 나눗셈시에 비트를 옮기는 것과 똑같은 결과를 가질 수 있다. 따라서 기존 거듭제곱을 » 로 바꾸면 성능 향상을 얻을 수 있다!

비트마스킹

비트마스킹은 각 비트를 하나의 flag 로 활용하는 것이다. A의 집합에 {0,2,5} 가 존재한다면 101001 로 나타낼 수 있다. NOT 을 사용하면 A 집합에 없는 원소들을 쉽게 알아낼 수 있다. B 집합은 100111 일 때 두 집합간의 합집합, 교집합 등을 비트 연산자로 빠르게 구할 수 있다.

데이터 압축

만약 문자열 두 개를 비교할 때 문자열이 알파벳만으로 이루어져있다면 1~26 의 숫자로 충분히 구별할 수 있다. 이는 하나 당 5개의 비트가지고 표현할 수 있다는 것이다. 따라서 각 char 에서 다섯 비트만 뽑아서 압축 저장해 비교할 수 있다. 이때 대소 비교 결과는 원래 문자열의 사전순 비교와 동일한 결과값을 가진다!

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;
}

실제 코드

실제 코딩 시 비트 연산을 사용했던 사례들이다. 아래의 코드들은 java 로 작성되었다.

        String strN = Integer.toString(N);
        for (int i = 0; i < strN.length(); i++) {
            int a = (1 << (strN.charAt(i) - '0'));
        }

135 를 입력받았으면 0B0000101010 으로 만들어주는 코드이다. 이때 strN.charAt(i) 의 값은 char 이기 때문에 해당 숫자를 그 숫자값으로 만들어주기 위해서는 ‘0’ 만큼 빼주는 작업이 필요하다!

int num = (1 << n);

2^n 의 값을 쉽게 구할 수 있다.

if (i & (1 << j)) {...}

i의 j 번째 비트가 1인지 아닌지를 의미한다. 처리할 값을 비트마스킹했다면 위를 통해 값의 존재여부를 확인할 수 있다!

업데이트:

댓글남기기

참고