LSB를 off하는 우아한 방법: Kernighan's Bit Trick

인생을 살다 보면 비트를 순회하며 LSB를 순차적으로 접근해야 할 일이 생긴다.

생각해보자.

• 1. 데이터의 LSB부터 비트를 순차적으로 참조해야 한다.
• 2. 비트가 on이라면, logic을 수행한다
• 3. 해당 비트를 off 해야한다

이런 상황에서 어떻게 접근할까?
아래와 같은 8비트 데이터가 있다고 생각해보자.

0010 0110

학부생 정도라면...

아마 이렇게 생각할것이다...(나라면)
lsb 부터 shift 연산으로 bit를 순회해볼까?

#include <stdio.h>

int main() {
    unsigned char a = 0b00100110;
    int index = 1, i = 0, bit = 0;
	while (i < sizeof(a) * 8) {
    	if (a & index) {
          // do something
          a ^= index;
        }
        index <<= 1;
        i++;
    }

    return 0;
}

하지만 여기에는 문제점이 있다.
그렇다. 전형적인 뇌는 편한데 컴퓨터는 힘든 완전순회 알고리즘이다.
8비트라면 다행이다. 근데 32비트라면? 64비트라면?
해당 로직이 한 번이 아닌 수만, 수억번, 그 이상 돌아간다면?
마냥 최선은 아닐 것이다.

비트 연산에 익숙한... 개발자라면

c개발 짬밥이 좀 있다면. gcc 등에서 제공하는 __builtin_ctz 종류를 알고 있을 것이다.
해당 함수는 값에서 처음으로 1이 나오기 전까지 0의 개수를 세어준다.
이걸 사용하면 코드가 좀 더 아름다워진다

#include <stdio.h>
#include <stdint.h>

int main() {
    unsigned char a = 0b00100110;
    int index = 1;

    while (a) {
    	index = __builtin_ctz(a);
        // do something
		a ^= (uint64_t)1 << index;
    }

    return 0;
}

나쁘진 않다. 실제로 많이 쓰이는 기법이기도 하고.
그런데 아직 살짝 아쉽다.
왜 아쉽냐고 한다면... while 내부의 연산이 직렬적으로 발생하기 때문이다.

말인즉슨

    	int index = __builtin_ctz(a); << 여기서 계산된 index가
        // do something << 여기도
		a ^= (uint64_t)1 << index; << 여기까지!

보이는가? while loop 내부에서 계산된 index가 로직 전체적으로 종속되어 사용된다.
컴파일러가 끼어들 부분이 없는 것이다.
그렇다면 어쩌면 좋을까?

바로 거기서
Kernighan's Bit Trick 이 등장한다.

Kernighan's Bit Trick

로직의 목적을 다시 한 번 생각해보자.

• 1. LSB의 위치를 찾아서 해당 위치에 대한 logic을 시행한다
• 2. LSB 를 off 한다

생각해보면, 이 두 연산은 결코 직렬적일 필요가 없다.
갸우뚱할수도 있겠다. 이런 질문을 할 수도 있다.

아니... LSB의 위치도 모르는데 어떻게 off하냐?

그래 맞다... 하지만 생각해보자. 결국 LSB를 끄는 것은. 그냥 데이터에서 가장 먼저 마주치는 비트를 off하면 되는거다.

바로 이렇게...

#include <stdio.h>

int main() {
    unsigned char a = 0b00100110;
	int index = 0;
    while (a) {
        index = __builtin_ctz(a);
        // do something
        a &= (a - 1); // 커니핸 트릭: 최하위 1 비트만 OFF
    }
    return 0;
}

뺄셈의 받아내림을 사용한 우아한 현상으로 index를 사용하는 logic과 LSB를 off하는 과정을 분리한 것이다!

  aggr        : 0 0 1 0 0 1 1 0  (38)
  aggr - 1    : 0 0 1 0 0 1 0 1  (37)
---------------------------------- [비트 AND 연산]
  aggr &= ... : 0 0 1 0 0 1 0 0  (36)

정말... 정말로 아름답다.

단순 아름다운 것이 아니다. 다시 로직을 보자

        index = __builtin_ctz(a);  << index 사용
        // do something  << index 사용
        a &= (a - 1);  << index 미사용

보이십니까...?

• 1. LSB의 위치를 찾아서 해당 위치에 대한 logic을 시행한다
• 2. LSB 를 off 한다

이 두 가지가 아름답게 분리되었어요.

즉, a를 업데이트하는 로직이 더 이상 index 변수에 데이터 의존성(Data Dependency) 을 가지지 않게 된 것입니다!!!

그 결과 컴파일러의 최적화는 물론, 현대 CPU 파이프라인에서 두 연산을 동시에 던져버리는 명령어 수준 병렬성(ILP)의 이점까지 극대화할 수 있게 됩니다.

정말 아름다운 기법이 아닐 수 없습니다. 저도 저절로 말투가 존댓말이 됩니다.