비트 연산 trick

요즘 운영체제 수업을 듣는다. 작년 이맘때에도 들었지만 중간에 휴학을 하는 바람에 다시 듣는다.

컴퓨터공학과에서 운영체제는 보통 3학년 1학기에 듣는 듯 하다. 막학기가 되어서야 듣는 나는 그만큼 기본기가 부족하다는 뜻이다.

 

다행히 존경스런 교수님이 정말 세세히 알려주셔서 감사한 마음으로 기본기를 쌓을 수 있다. 실습은 항상 1등으로 풀고 나가지만 여기서 만족하지 않고 더 열심히 해나가야겠다.

 

아무쪼록, 실습 내용을 앞으로는 그날그날 간단히 정리를 해보려고 한다. 친숙하지만, 그 속에 많은 유용한 정보를 담고 있을 수 있다.

 

 

가장 첫 번째는 비트 연산이다.

 

컴퓨터는 태생적으로 0과 1로밖에 데이터를 저장하지 못하기 때문에, 이진법을 필연적으로 사용할 수밖에 없다.

컴파일러마다 약간 차이가 있긴 하지만 char은 8비트, short는 16비트, int는 32비트, long long은 64비트를 쓴다.

당연히 표현 범위는 2^(비트 갯수) - 1가지. 음수를 표현하지 않는 unsigned와, 맨 앞 1비트를 부호로 표시하는 signed 두 가지가 있는 것은 누구나 잘 알 것이다.

 

따라서 비트로 작동하는 컴퓨터를 사용할 때, 비트 연산과 친해지는 것은 기본 중 기본이라고 생각한다. 이에 몇 가지 신기한 비트 연산 트릭을 소개한다. 유용함을 넘어, 아름답기까지 한 것들이 많다.

 

1) 새로운 변수 선언 없이 swap하기 (XOR 이용)

int a = 3, b = 10;
a ^= b;
b ^= a;
a ^= b; // now, a = 10, b = 3

가장 유명한 것일 듯한 XOR을 이용한 swap이다.

기본적으로 XOR은 다음과 같은 성질이 성립한다.

 

a^0 = a

a^a = 0

a^b = b^a (교환 법칙)

(a^b)^c = a^(b^c) (결합 법칙)

 

즉, 계산 순서에 상관없이 숫자가 중첩된 횟수에만 상관있다. 실로 아름다운 연산자이다.

 

 

2) + 연산자 없이 두 수 더하기

int add(int x, int y) {
	while (y) {
		int z = x & y;
		x ^= y;
		y = z << 1;
	}
}

아름다운 식이다.

간단히 설명하면 두 수를 "비트가 겹치는 부분"과 "아닌 부분"으로 나누어,

아닌 부분은 그냥 더하고

겹치는 부분은 받아올림 해주는 과정을 반복하는 것이다.

 

 

3) 가장 아래 켜진 비트를 제거

x &= x - 1;

 

간단하지만 생각하기 어려운 식이다.

01010100 // x

01010011 // x - 1

01010000 // x & (x - 1)

원리를 살펴보면 자명하다.

 

이는 여러 가지로 활용될 수 있는데, 예컨데

 

숫자가 2의 거듭제곱인지:

if (x & (x - 1))

켜진 비트의 수 세기:

for (cnt = 0; x; ++cnt) x &= x - 1;

등으로 활용할 수 있겠다.

 

 

4) 켜진 비트의 모든 부분집합 순회

a | b == a일 때, b는 a의 부분집합이라고 하자.

(예를 들어 이진수 1001의 부분집합은 1001, 1000, 0001, 0000 4가지가 있겠다)

총 2^(켜진 비트 수)개의 부분집합을 간단하게 순회하는 법이 존재할까?

 

존재한다.

int a = 23;
for (int b = a; b; b = a & (b - 1)) {
	cout << b << '\n';
}

코드를 차근차근 읽으며 감상해보자.

참고로 아쉽게도 0은 순회하지 않는다. do-while을 쓰면 0도 포함하는 것이 가능하다.

 

 

5) 그 외 (썩은물 버전)

그 외에도 이것저것 많이 존재하는데.. 쓸 일은 거의 없을 듯 하다.

그냥 이런 식으로 생각할 수 있다는 것에 의의를 두자.

 

unsigned char의 비트를 reverse하려면 어떻게 해야 할까?

(예시. 10000010 ->01000001)

보통 for문을 돌리는 것을 생각하겠지만, 기상천외한 방법이 있다.

 

바로 

unsigned char b;
 
b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

이 코드이다.

 

어떻게 작동하는지조차 감잡기 힘든 이 코드는 다음과 같은 원리로 작동한다.

이러한 창의적인 생각을 할 수 있다는 것에 놀라자.

일부 내용 출처: http://graphics.stanford.edu/~seander/bithacks.html