병렬 비트 카운팅(Parallel Bit Counting)

본 문서는 다음의 내용을 번역한 것이다. http://bits.stephan-brumme.com/countBits.html

001: unsigned int countBits(unsigned int x)
02: {
03:   // count bits of each 2-bit chunk
04:   x  = x - ((x >> 1) & 0x55555555);
05:   // count bits of each 4-bit chunk
06:   x  = (x & 0x33333333) + ((x >> 2) & 0x33333333);
07:   // count bits of each 8-bit chunk
08:   x  = x + (x >> 4);
09:   // mask out junk
10:   x &= 0xF0F0F0F;
11:   // add all four 8-bit chunks
12:   return (x * 0x01010101) >> 24;
13: }
14:
15: unsigned int countBitsLoop(unsigned int x)
16: {
17:   unsigned int result = 0;
18:   // strip one set bit per iteration
19:   while (x != 0)
20:   {
21:   x &= x-1;
22:   result++;
23:   }
24:   return result;
25: }

설명

countBits 함수(1 - 13 번째 행)

정수의 모든 설정된 비트들을 세는 것은 많은 메인 프레임 CPU의 어셈블리 언어의 일부였지만, 몇몇 x86 계열 CPU들은 그것을 수십년 간 무시해왔다. 명백히 Intel은 POPCNT 연산코드(opcode)를 Core i7 설계 과정에서 도입했다.

한편, 해밍 가중치(population count, Hamming weight)는 다른 방식으로 구현되어져야 했다.

주요 발견은 우리가 특정 비트 블락을 작은 청크들로 쪼개고 그것의 해밍 가중치들을 계산하고 중간 값들을 모두 더한다는 사실에 기반을 두고 있다.

첫째, 이 코드는 인접한 두 비트들의 갯수를 센다.

0b와 0b → 00b

0b와 1b → 01b

1b와 0b → 10b

1b와 1b → 11b

전체 알고리즘은 출력을 생성하기 위해서 입력을 변형한다. 이 말은 이것이 따로 공간을 안 만들고 해당 변수에 대해 즉시(in-place) 동작한다는 뜻이다.

4번째 행은 발견의 근거하여 2비트 세기 연산을 한 번에 수행한다.

00b → 안 바뀌고, 여전히 00b

01b → 안 바뀌고, 여전히 01b

10b → 01b로 바뀌어져야 함

11b → 10b로 바뀌어져야 함

각 2-비트 그룹의 상위 비트가 설정될 때, 01b를 빼는 것이 원하는 결과를 얻을 수 있게 해준다.

브랜칭처럼 보이지만 ... 그것은 결국, 빼기 연산이 언제나 행해질 수 있다는 것으로 귀결된다: 단지 상위 비트를 뺀다!

만약 그것이 0이면, 결과는 변하지 않지만, 만약 그것이 1이면, 우리는 적합한 숫자를 얻는다.

x >> 1 쉬프트 연산과 다음의 모든 홀수 비트가 설정된 마스크 (0x55는 01010101b임)는 다음과 같이 계산된다.

00b → 쉬프트 연산 후: ?0b → 마스크와 AND 연산 후: 00b → 빼기 연산과 비교: 00b − 00b → 00b

01b → 쉬프트 연산 후: ?0b → 마스크와 AND 연산 후: 00b → 빼기 연산과 비교: 01b − 00b → 01b

10b → 쉬프트 연산 후: ?1b → 마스크와 AND 연산 후: 01b → 빼기 연산과 비교: 10b − 01b → 01b

11b → 쉬프트 연산 후: ?1b → 마스크와 AND 연산 후: 01b → 빼기 연산과 비교: 11b − 01b → 10b

이제 2-비트별 세기 연산이 완료되었다. 여기서 알 수 있듯이, 오직 세 가지의 가능한 10진수 결과 값이 있을 수 있다: 0, 1, 2.

다음에, 인접한 2-비트 그룹들이 4-비트 그룹들로 합쳐진다(6번째 행):

00b과 00b → 0000b

00b과 01b → 0001b

00b과 10b → 0010b

01b과 00b → 0001b

01b과 01b → 0010b

01b과 10b → 0011b

10b과 00b → 0010b

10b과 01b → 0011b

10b과 10b → 0100b

이번에는, 2-비트 그룹들에 AND 마스크 연산을 수행하고, 비트 순서 일치를 위해서 쉬프트 연산을 수행한 뒤 단순히 더하고 있다. 오버플로우는 일어나지 않는다.

00b + 00b → 0000b

00b + 01b → 0001b

00b + 10b → 0010b

01b + 00b → 0001b

01b + 01b → 0010b

01b + 10b → 0011b

10b + 00b → 0010b

10b + 01b → 0011b

10b + 10b → 0100b

동일한 단계를 모든 4-비트 그룹들에 대해서 적용하면 각 4 바이트의 비트 갯수가 하위 4 비트 값들에 저장된다(8번째 행). 이것이 의미하는 바는, 각 바이트는 그것의 비트 갯수를 저장하고 있지만, 상위 4 비트들은 아마 불필요한 값을 가지고 있을 것이기에 제거한다(10번째 행).

0x01010101으로 곱하는 것은 흥미로운 특성을 가지고 있다. 만약 우리가 4 바이트를 A, B, C, D라고 이름 지으면 다음과 같이 표현된다:

A, B, C, D → A+B+C+D, B+C+D, C+D, D

명백히 최상위 바이트가 우리가 찾으려는 값이다. 오른쪽 쉬프트 연산(12번째 행)은 단지 그것을 반환한다.

countBitsLoop 함수(15 - 25번째 행)

매우 우아하고 종종 더 빠른 알고리즘이 브라이언 커니헌과 데니스 릿치(Brian Kernighan, Dennis Ritchie)의 유명한 책 "C 프로그래밍 언어(The C Programming Language)"에 소개되었다. 인터넷을 통해서 피터 웨그너(Peter Wegner)가 처음으로 그것을 공개했다는 것을 알았다.

다른 알고리즘과 다르게, 그것의 성능은 입력에 매우 강하게 의존한다. 대략 4 비트이하로 설정되면, 그것은 모든 다른 알고리즘보다 훨씬 높은 성능을 보이지만, 대부분의 비트들이 설정된 경우 심각하게 나빠진다.

중요한 트릭인 단일 비트를 x &= x - 1로 제거해 내는 것이다(21번째 행)에 관심을 두어야할 필요가 있다:

만약 x = 0이면, while 루프에 전혀 들어가지 않기 때문에 우리는 이 경우를 고려할 필요가 없다
만약 가장 오른쪽 비트가 1이면, x - 1의 가장 오른쪽 비트는 0이다. 모든 다른 비트들은 동일하고 x &= x − 1 → x = x − 1이다. 모든 다른 비트들이 동일하기 때문에 우리는 가장 오른쪽에 있는 하나의 설정된 비트를 제거한다.
만약 가장 오른쪽에 있는 비트들이 0이면, x는 다음과 같이 보일 것이다: ...1000. 그리고 x − 1은 다음과 같이 보일 것이다: ...0111. x &= x-1의 결과는 다음과 같을 것이다: ...0000. 그런 까닭에, x &= x − 1은 점(.)으로 표시된 비트들을 제외한 모든 다른 비트들을 0으로 설정한다. 점으로 표시된 부분은 그대로 남는다. 다시 말하면, 정확히 한 비트만이 0으로 설정되었다.
일반적으로, x &= x − 1는 1이었던 가장 오른쪽 비트를 언제나 0으로 설정한다.

제한 사항

32비트에서 동작하도록 고안되었다
countBitsLoop 함수의 경우엔 모든 비트 길이에 상관 없이 동작할 수 있다.

성능 평가

Intel® Pentium™ D:

countBits: ≈ 23 싸이클/숫자, 상수 시간, 데이터에 무관
countBitsLoop: ≈ 68 싸이클/숫자 (평균)
countBitsLoop(0): ≈ 4 싸이클/숫자, 0개 비트가 설정되었을 때(0%가 설정)
countBitsLoop(16): ≈ 54 싸이클/숫자, 16개 비트가 설정되었을 때(50%가 설정)
countBitsLoop(32): ≈ 145 싸이클/숫자, 32개 비트가 설정되었을 때(100%가 설정)
simple (풀어진 for-루프): ≈ 60 싸이클/숫자, 상수 시간, 데이터에 무관

Intel® Core™ 2:

countBits: ≈ 16.5 싸이클/숫자, 상수 시간, 데이터에 무관
countBitsLoop: ≈ 37.5 싸이클/숫자 (평균)
countBitsLoop(0): ≈ 2.5 싸이클/숫자, 0개 비트가 설정되었을 때(0%가 설정)
countBitsLoop(16): ≈ 37 싸이클/숫자, 16개 비트가 설정되었을 때(50%가 설정)
countBitsLoop(32): ≈ 70 싸이클/숫자, 32개 비트가 설정되었을 때(100%가 설정)
simple (풀어진 for-loop): ≈ 77 싸이클/숫자, 상수 시간, 데이터에 무관

Intel® Core™ i7:

countBits: ≈ 16 싸이클/숫자, 상수 시간, 데이터에 무관
countBitsLoop: ≈ 38 싸이클/숫자 (평균)
countBitsLoop(0): ≈ 2.5 싸이클/숫자, 0개 비트가 설정되었을 때(0%가 설정)
countBitsLoop(16): ≈ 37 싸이클/숫자, 16개 비트가 설정되었을 때(50%가 설정)
countBitsLoop(32): ≈ 70 싸이클/숫자, 32개 비트가 설정되었을 때(100%가 설정)
simple (풀어진 for-loop): ≈ 67 싸이클/숫자, 상수 시간, 데이터에 무관

어셈블러 출력

countBits:
compiler: VC 2008
in: eax ← x
out: eax → result
temp: ecx
01:   ; x = x - ((x >> 1) & 0x55555555)
02:   mov ecx, eax
03:   shr ecx, 1
04:   and ecx, 55555555h
05:   sub eax, ecx
06:   ; x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
07:   mov ecx, eax
08:   and eax, 33333333h
09:   shr ecx, 2
10:   and ecx, 33333333h
11:   add ecx, eax
12:   ; x = x + (x >> 4)
13:   mov eax, ecx
14:   shr eax, 4
15:   add eax, ecx
16:   ; x &= 0xF0F0F0F
17:   and eax, 0F0F0F0Fh
18:   ; (x * 0x01010101) >> 24
19:   imul eax, 01010101h
20:   shr eax, 24

countBitsLoop:
compiler: VC 2008
in: ecx ← x
out: eax → result
temp: edx
01:   ; result = 0
02:   xor eax, eax
03:   ; while (x != 0)
04:   test ecx, ecx
05:   je $finish
06: $while:
07:   ; x &= x-1
08:   lea edx, [ecx-1] ; clever x86 trick: edx = ecx-1
09:   and ecx, edx
10:   ; result++
11:   inc eax
12:   test ecx, ecx
13:   jne $while
14: $finish:

다운로드

테스트 프로그램을 포함한 전체 소스코드가 다운로드 가능하다.

countBits.cpp

참고

AMD, "AMD64 프로세서용 AMD 소프트웨어 최적화 가이드"

피터 웨그너(Peter Wegner): "이진 컴퓨터에서 1을 세는 기술(A Technique for Counting Ones in a Binary Computer)", Communications of the ACM, Volume 3 (1960) Number 5, page 322

다음은 http://chessprogramming.wikispaces.com/Population+Count#SWAR-Popcount-Counting%20Duo-Bits을 번역한 내용의 일부이다.

쌍-비트 세기

한 비트-쌍(두 인접한 비트들)은 0 = a, 1 = b로 해석될 수 있다.

쌍의 갯수는 다음과 같이 정의된다.

이것은 다음과 같이 표현될 수 있다.

또는

비트-쌍은 갯수를 세는 과정에서 아래 표에 나타난 것처럼 2진수로는 0에서 2까지 네 가지 상태를 가지고 있다:

x	-	x div 2	→	popcnt(x)
00	-	00	→	00
01	-	00	→	01
10	-	01	→	01
11	-	01	→	10

오직 하위의 비트가 x div 2 -에서 필요하고, 우리는 이웃 쌍에서 가져오는 것을 걱정할 필요가 없다. SWAR-방식(SIMD with in a register, 다중 데이터 단일 명령처리를 한 레지스터 안에서 수행하는 방식)으로 우리는 32개의 2비트 쌍들의 64비트 빼기 연산을 수행하기 위해서 2로 나눠진 피차수(빼기 기호 뒷부분)의 모든 "짝수" 비트들을 초기화할 필요가 있다.

x = x - ((x >> 1) & 0x5555555555555555);

비트-쌍들을 세기 과정은 여전히 두개의 비트들을 취함을 주의하자.

니블(4) 비트 세기

다음 단계는 4-비트의 이웃 비트의 갯수, 16개의 니블 비트 수를 세기 위해서 2-비트의 세기 결과를 더하는 것이다. 이 값은 아마 0에서 4개의 값을 가질 것이다. SWAR-방식으로 이것은 홀수를 마스킹하고, 그들을 같이 더하기 위해서 2-비트 쌍들을 함께 더한다.

x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);

니블 비트들의 갯수 세기 결과들은 오직 3 비트만을 취하기 때문에 100B가 최대 셀 수 있는 갯수이다(1111B 니블 비트의).

바이트 갯수

이미 어떻게 하는지 알게 되셨는지요? 이제 그것은 두 니블 비트 단위의 갯수로부터 바이트 단위의 갯수를 얻을 차례이다. 최대 바이트 단위 갯수인 1000B는 오직 4 비트들만을 취하고, 그래서 피가수를 만드는 것 대신에 덧셈 결과의 4비트에 마스크를 취하는 것이 안전하다.

x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;

바이트 갯수 더하기

우리는 아마 바이트 갯수 덧셈, 워드 갯수, 그리고 끝으로 더블 워드 갯수를 세는 과정에서 최종 결과의 낮은 자리 8(또는 7) 비트가 0에서 64 범위에 있도록 마스크를 하기 위해서 마스크가 없는 병렬 접두사(http://chessprogramming.wikispaces.com/Parallel+Prefix+Algorithms) SWAR 덧셈을 할 수도 있다.

x += (x >> 8);

x += (x >> 16);

x += (x >> 32);

return x & 255;

곱하기

오늘날의 빠른 64비트 곱샘기와 함께 우리는 최상위 비트 값에 있는 최종 결과 값을 얻기 위해서 8바이트 셈 벡터를 0x0101010101010101를 곱하고, 다음으로 오른쪽 쉬프트를 수행한다:

x = (x * 0x0101010101010101) >> 56;

솎아 내기(Casting out)

흥미롭게도, 바이트 결과를 더하는 다른 접근법이 있다. 십진수 수(10을 기준값)와 9값들을 솎아내기(http://en.wikipedia.org/wiki/Casting_out_nines)dptj qhdlemtdl, 기준 값에 의한 나머지(modulo, http://chessprogramming.wikispaces.com/General+Setwise+Operations#Modulo) 연산 결과로 솎아진 값에 1을 뺀 값은 개별 숫자 덧셈(http://en.wikipedia.org/wiki/Digit_sum)과 같다. 부연하자면, 가령, 84001의 개별 숫자 덧셈은 8+4+0+0+1 = 13 이다. 이것은 낮은 범위인 0..8의 "256" 기준 값의 숫자들에 적용할 수 있다:

x = x % 255;

하지만, 나눗셈과 나머지 연산은 일반적으로 느린 연산이고 상수에 의한 나머지 연산은 컴파일러에 의해서 상보적인 연산으로 대체되기 쉽다. 0x0101010101010101을 곱하는 경우는 2-adic(http://en.wikipedia.org/wiki/P-adic_number) 분수인 -1/255가 선호되는 방법이다.

비트수 계산 루틴(PopCount 루틴)

상수

모두 함께 두면, 다양한, SWAR-마스크들과 요소값들은 도널드 누스(Donald Knuth) 교수님에 의해서 2-adic 분수로 선언되었다.

const U64 k1 = C64(0x5555555555555555); /*  -1/3   */
const U64 k2 = C64(0x3333333333333333); /*  -1/5   */
const U64 k4 = C64(0x0f0f0f0f0f0f0f0f); /*  -1/17  */
const U64 kf = C64(0x0101010101010101); /*  -1/255 */

비트 보드에서 다음과 같이 표현된다.

k1 -1/3 k2 -1/5 k4 -1/17 kf -1/255

0x5555555555555555 0x3333333333333333 0x0f0f0f0f0f0f0f0f 0x0101010101010101

1 . 1 . 1 . 1 . 1 1 . . 1 1 . . 1 1 1 1 . . . . 1 . . . . . . .

popCount 함수

이것은 전체 루틴이 C 언어에서 어떻게 보이는지 보인다:

int popCount (U64 x) {
    x =  x       - ((x >> 1)  & k1); /* put count of each 2 bits into those 2 bits */
    x = (x & k2) + ((x >> 2)  & k2); /* put count of each 4 bits into those 4 bits */
    x = (x       +  (x >> 4)) & k4 ; /* put count of each 8 bits into those 8 bits */
    x = (x * kf) >> 56; /* returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...  */
    return (int) x;
}

장점: 브랜치가 없고, 메모리 룩없이 없고, 상수 런타임을 가지며 - 갯수에 상관이 없다

단점: 체인에 의존하며,큰 병렬 성능 상승이 없다.

slowmul_popCount 함수

그리고, 이전에 시작했듯이, 상대적으로 느린 곱셈기를 가진 컴퓨터들에서는 대안으로 수동적인 덧셈을 할 수 있다.

int slowmul_popCount (U64 x) {
    x =  x       - ((x >> 1)  & k1); /* put count of each 2 bits into those 2 bits */
    x = (x & k2) + ((x >> 2)  & k2); /* put count of each 4 bits into those 4 bits */
    x = (x       +  (x >> 4)) & k4 ; /* put count of each 8 bits into those 8 bits */
    x += x >>  8;  /* put count of each 16 bits into their lowest 8 bits */
    x += x >> 16;  /* put count of each 32 bits into their lowest 8 bits */
    x += x >> 32;  /* put count of the final 64 bits into the lowest 8 bits */
    return (int) x & 255;
}

성긴 비트보드들을 가지고 있는 숫자들의 경우, 루프 방식의 브라이언 커니헌(Brian Kernighan)의 방식(http://chessprogramming.wikispaces.com/Population+Count#BrianKernighansway)이 더 빠를 것이다.

HAKMEM 169

유사한 기술이 MIT(http://chessprogramming.wikispaces.com/Massachusetts+Institute+of+Technology)의 빌 고스퍼(Bill Gosper, http://chessprogramming.wikispaces.com/Bill+Gosper) 등에 의해서 1972년에 출판된 Memo 239(HAKMEM, http://en.wikipedia.org/wiki/HAKMEM) 제안되었다. 여기에서는 두-비트 쌍을 연속적으로 더하는 것 대신 3-비트쌍을 더했고, 32비트 버전은 63으로 솎아내는 것에 의존한다. 주의할 것은 아래의 코드에서 상수는 8진수(Octal, http://en.wikipedia.org/wiki/Octal, 기준 값 8)을 가지고 있고, PDP-6(http://chessprogramming.wikispaces.com/PDP-6)을 위해서 어셈블리어(http://chessprogramming.wikispaces.com/Assembly#HAKMEM169)로 쓰였다. 확장된 64 비트 버전은, 511 또는 4095로 솎아내며, 위의 이진 SWAR 버전 보다 약간 덜 효율적이다.

int hakmem169_32(unsigned int x) {
   x = x  - ((x >> 1)  & 033333333333)
          - ((x >> 2)  & 011111111111);
   x = (x +  (x >> 3)) & 030707070707 ;
   return x % 63; /* casting out 63 */
}

기타

다중 집합의 원소 갯수(Cardinality)

만약 우리가 집합의 배열들을 세기(http://chessprogramming.wikispaces.com/Array) 원한다면, 우리는 odd-major-트릭을 사용해서 2^N-1의 비트 갯수 세기 연산을 N개의 세기 연산으로 줄일 수 있다. 3 집합을 세기 위해서 하나를 세지 않고, 추가적인 5개의 쉬운 연산으로 대체할 수 있다.

odd = (x ^ y) ^ z;

major = ((x ^ y ) & z) | (x & y);

popCount(x) + popCount(y) + popCount(z) == 2*popCount(major) + popCount(odd)

합쳐진 popCount3 연산은 더 많은 병렬의 속도 향상을 얻을 것이다. 왜냐하면, 거기에는 독립적인 두개의 계산해야할 체인이 있기 때문이다. 적용 가능항 응용은 양쪽 비숍들의 조합을(왜냐하면 일반적으로 비숍들은 거의 대부분 다른 사각형 색상을 가짐으로 인해 서로소 집합들을 가지기 때문이다.) 두 나이트 이동 대상 집합 쪽으로 넘기는 곳에 쓸 수 있다.

// return popCount(x) + popCount(y) + popCount(z)
int popCount3 (U64 x, U64 y, U64 z) {
    U64 maj = ((x ^ y ) & z) | (x & y);
    U64 odd = ((x ^ y ) ^ z);
    maj =  maj - ((maj >> 1) & k1 );
    odd =  odd - ((odd >> 1) & k1 );
    maj = (maj & k2) + ((maj >> 2) & k2);
    odd = (odd & k2) + ((odd >> 2) & k2);
    maj = (maj + (maj >> 4)) & k4;
    odd = (odd + (odd >> 4)) & k4;
    odd = ((maj + maj + odd) * kf ) >> 56;
    return (int) odd;
}

Odd와 Major 7-15 방법

물론 7번의 비트 갯수 세기 연산을 3개로,혹은 심지어 15개의 비트 세기 연산을 4개로 줄이는 것은 훨씬 더 흥미로워 보인다.

N = 2^n -1에 대해서, 그것은 N - n odd-major 쌍을 취한다. 그런 까닭에 하나의 add-major 쌍(5개의 연산들)이 popCount 수행 마다 절약된다.

그것은 7 - 3 = 4쌍들이다:

one1,two1 := oddMaj(x1,x2,x3)

one2,two2 := oddMaj(x4,x5,x6)

ones,two3 := oddMaj(x7,one1,one2)

twos,four := oddMaj(two1,two2,two3)

혹은 15 - 4 = 11 쌍들이다:

one1,two1 := oddMaj(x1,x2,x3)

one2,two2 := oddMaj(x4,x5,x6)

one3,two3 := oddMaj(x7,x8,x9)

one4,two4 := oddMaj(x10,x11,x12)

one5,two5 := oddMaj(x13,x14,x15)

one6,two6 := oddMaj(one1,one2,one3)

ones,two7 := oddMaj(one4,one5,one6)

two8,four1 := oddMaj(two1,two2,two3)

two9,four2 := oddMaj(two4,two5,two6)

twos,four3 := oddMaj(two7,two8,two9)

four,eight := oddMaj(four1,four2,four3)

Odd와 Major 개별 숫자 덧셈

Odd-Major 방법은 아마도 공격이나 다른 것들에 대한 개별 숫자 덧셈 집합을 결정하는데 유용할 것이다.

U64 odd(U64 x, U64 y, U64 z) {return x^y^z;}
U64 maj(U64 x, U64 y, U64 z) {return ((x^y)&z)|(x&y);}
 
void attackCounts(U64 t[3], const U64 s[7]) {
   one1 = odd(s[0], s[1], s[2]);
   two1 = maj(s[0], s[1], s[2]);
   one2 = odd(s[3], s[4], s[5]);
   two2 = maj(s[3], s[4], s[5]);
   t[0] = odd(s[6], one1, one2);
   two3 = maj(s[6], one1, one2);
   t[1] = odd(two1, two2, two3);
   t[2] = maj(two1, two2, two3);
}

이것은 다음의 의미를 가진다.

exactly7attacks := t[2] & t[1] & t[0]

exactly6attacks := t[2] & t[1] & ~t[0]

exactly5attacks := t[2] & ~t[1] & t[0]

exactly4attacks := t[2] & ~t[1] & ~t[0]

exactly3attacks := ~t[2] & t[1] & t[0]

exactly2attacks := ~t[2] & t[1] & ~t[0]

exactly1attack := ~t[2] & ~t[1] & t[0]

noAttack := ~t[2] & ~t[1] & ~t[0]

atLeast4attacks := t[2]

atLeast2attacks := atLeast4attacks | t[1]

atLeast1attack := atLeast2attacks | t[0]

noAttack := ~atLeast1attack

exactly1attack := atLeast1attack ^ atLeast2attacks

LS1B의 log2로써의 PopCount

빠른 popcount-연산(하지만 비트 스캔이 없음)을 가진 아키텍쳐를 고려해 보자. 우리는 로그 이원성을 계산하기 위해서 LS1B를 따로 빼낼 수 있고, 감소 시키고 남아 있는 "1"의 값들을 셀 수 있다.

log2(LS1B) = popCount( LS1B - 1 );

bitIndexOfLS1B(x) = popCount( (x & -x) - 1 );

예를 들어, LS1B는 2^44이라면, 감소 연산은 LSB1 마스크의 아래 44 비트가 설정되게 한다.

0x0000100000000000 0x00000FFFFFFFFFFF

. . . . . . . . . . . . . . . .

. . . . 1 . . . 1 1 1 1 . . . .

. . . . . . . . 1 1 1 1 1 1 1 1

해밍 거리

두 워드의 해밍 거리(http://en.wikipedia.org/wiki/Hamming_distance)는 대응되는 다른 비트의 수(http://chessprogramming.wikispaces.com/General+Setwise+Operations#ExclusiveOr)로 정의된다.

int hammingDistance (U64 a, U64 b) {return popcnt( a ^ b);}

1이나 2보다 큰 해밍 거리는 1 비트 에러들을 감지하거나 심지어 고칠 수 있는 중요한 속성이다.

최소 그리고 평균 해밍 거리는 조브리스트(Zobrist) 키들(http://chessprogramming.wikispaces.com/Zobrist+Hashing)에 대해서 키의 "품질"-척도로 여겨진다. 하지만, 최소 해밍 거리가 0보다 큰 경우, 선형 독립성(http://en.wikipedia.org/wiki/Linear_independence)이 해밍 거리 보다 더 중요하다. 선형 독립성은 XOR 연산 후 0이 되지 않는 모든 키들의 작은 부분 집합이다. 최소 해밍 거리를 최대화하는 것은 매우 안좋은 조브리스트 키를 생성한다.

가중치 PopCount

SIMD-방식(http://chessprogramming.wikispaces.com/SIMD+and+SWAR+Techniques) 종류의 가중치 비트 갯수 세기를 위해서라면, SSE2 내적(http://chessprogramming.wikispaces.com/SSE2#SSE2dotproduct)을 참고하라.

미리 계산된 이동성

자리 차지 검색으로 공격하기(http://chessprogramming.wikispaces.com/Sliding+Piece+Attacks#AttacksbyOccupancyLookup)와 유하게, 움직이는 말들의 공격 집합을 결정하기 위해서, 우리는 아마 미리 계산된 비트 갯수 세기를 사용하거나 심지어는 중간값 가중치화된 비트 게산을 말의 이동성(http://chessprogramming.wikispaces.com/Mobility)의 대략적인 예측을 위해서 사용한다. 그것은 아마 소위 말하는 안전한 대상 사각 지대의 부분 집합을 고려하지 않는다.

말 공격 갯수

마르코 코스탈바(http://chessprogramming.wikispaces.com/Marco+Costalba)에 의해서 제안되었듯이, 왕(http://chessprogramming.wikispaces.com/King), 기사(http://chessprogramming.wikispaces.com/Knight)의 공격의 비트 개수 (이동성, http://chessprogramming.wikispaces.com/Mobility) 그리고 행 기반 말의 이동 가능한 부분 집합을 구하기 위해 특별히 고안된 루틴들은 일반적인 SWAR-비트 세기(http://chessprogramming.wikispaces.com/Population+Count#SWARPopcount) 보다 더 효율적으로 수행될 수 있다. 이것은 거울화 비트 뒤집고 돌리기(http://chessprogramming.wikispaces.com/Flipping+Mirroring+and+Rotating), 전체 비트 보드에 대해서 랭크, 파일과 대각에 대비하는 것과 유사하며, 단일 바이트 찾아보기(http://chessprogramming.wikispaces.com/Population+Count#Lookup)을 수행하기 위해서 8개까지의 분산되어 존재하는 1 바이트를 매핑하는 것에 기반을 두고 있다., 다양한 매핑 기술을 위해서는 다음을 참고하기 바란다:

비트 보드 직렬화(http://chessprogramming.wikispaces.com/Bitboard+Serialization)에서 온 다중 비트들 해싱하기(http://chessprogramming.wikispaces.com/Bitboard+Serialization#HashingMultipleBits)
거울화 뒤집고 돌리기(http://chessprogramming.wikispaces.com/Flipping+Mirroring+and+Rotating)에서 온 랭크, 파일과 대각(http://chessprogramming.wikispaces.com/Flipping+Mirroring+and+Rotating#RankFileAndDiagonal)
임의의 행 차지하기(http://chessprogramming.wikispaces.com/Occupancy+of+any+Line)

더 보기

비트 배배 꼬기(http://chessprogramming.wikispaces.com/Bit-Twiddling)
일반적인 셋기반 연산(http://chessprogramming.wikispaces.com/General+Setwise+Operations)에서 온 하나 이상의 큰 값을 가진 집합 방법(http://chessprogramming.wikispaces.com/General+Setwise+Operations#GreaterOne)
MMX 비트 수 세기(http://chessprogramming.wikispaces.com/MMX#MMXPopcount)
SMD와 SWAR 기술(http://chessprogramming.wikispaces.com/SIMD+and+SWAR+Techniques)
SSE 비트 수 세기(http://chessprogramming.wikispaces.com/SSE2#SSE2popcount)
SSE4.2(http://chessprogramming.wikispaces.com/SSE4#SSE4.2)
SSE4a(http://chessprogramming.wikispaces.com/SSE4#SSE4a)

다음은 스탠포드 대학 비트 핵에 있는 비트 집합의 갯수 세기 코드 중 일부 관심 있는 코드 부분(http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64)이다.

64 비트 명령을 이용해서 14, 24, 혹은 32-비트 워드의 비트 집합 갯수 세기

unsigned int v; // count the number of bits set in v

unsigned int c; // c accumulates the total bits set in v

// 선택 사항 1, v에서 최대 14-비트의 값:

c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// 선택 사항 2, v에서 최대 24-비트의 값:

c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)

% 0x1f;

// 선택 사항 3, v에서 최대 32-비트의 값:

c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %

0x1f;

c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

이 메서드는 효율적인 수행을 위해서 빠른 나머지 나누기 연산을 가진 64 비트 CPU를 요구한다. 첫째 선택 사항은 오직 3 연산이 필요하며, 두번째는 10, 세번째는 15의 연산이 필요하다.

리치 슈로펠(Rich Schroeppel)은 원래 선택사항 1과 유사한 9비트 버전을 만들었다; 빌러, 엠,(Beeler, M.), 고스퍼, 알. 더블유(Gosper, R. W.), 슈로에펠, 알(Schroeppel, R.)의 HAKMEM, MIT AI Memo 239, 2월 29일 1972년의 프로그래밍 핵(the Programming Hacks)의 절을 참조하라. 그의 방법은 위에 보이는 다른 변이가 생기도록 자극했으며, 션 앤더슨(Sean Anderson)에 의해서 고안되었다. 랜덜 이. 브라이언트(Randal E. Bryant)는 2005년 5월 3일에 다수의 버그 수정을 제공했다. 브루스 도우슨(Bruce Dawson)은 2007년 2월 1일에 12 비트 버전을 수정해서 같은 연산 수로 14 비트까지 사용할 수 있도록 했다.

비트 집합 병렬로 세기

unsigned int v; // count bits set in this (32-bit value)

unsigned int c; // store the total here

static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers

static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

c = v - ((v >> 1) & B[0]);

c = ((c >> S[1]) & B[1]) + (c & B[1]);

c = ((c >> S[2]) + c) & B[2];

c = ((c >> S[3]) + c) & B[3];

c = ((c >> S[4]) + c) & B[4];

B 배열은, 이진 수로 다음과 같이 표현된다.

B[0] = 0x55555555 = 01010101 01010101 01010101 01010101

B[1] = 0x33333333 = 00110011 00110011 00110011 00110011

B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111

B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111

B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111

우리는 이진 마법 숫자들의 패턴을 가지는 B와 S를 가지고 더 커다란 정수에 대한 메서드를 만들 수 있다. 만약, 거기에 k 비트가 있다면, 우리는 ceil(lg(k))의 요소 갯수를 가지는 S와 B 배열을 필요로하고, 우리는 S 혹은 B의 길이를 가지는 같은 갯수의 c에 대한 표현을 계산해야 한다. 32 비트 v를 위해서는 16 연산이 사용된다.

32 비트 정수 v를 세는 최선의 방법은 다음과 같다.

v = v - ((v >> 1) & 0x55555555); // 입력을 임시적으로 재사용

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // 임시

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // 갯수

최선의 비트 세기 연산은 오직 12 연산만을 소비하며, 이는 룩업 테이블 방법과 같지만, 메모리를 사용하지 않고 잠재적으로 발생하는 테이블의 캐시가 존재하지 않는 것을 피할 수 있다. 이것은 완전 병렬 방법과 곱하기를 사용하는 방식의 혼합 방식이다(64-비트 명령으로 비트들 세기 절에 있는). 비록 그것이 64비트 명령을 사용하지는 않지만 말이다. 비트 집합의 갯수를 세는 것은 병렬로 수행되고, 바이트 상의 비트 집합의 전체 합은 0x1010101을 곱하고 24 비트를 오른쪽 쉬프팅함으로써 얻어진다.

128비트까지(타입 T로 파라미터화 되었다) 일반화된 최선의 비트 갯수 세기 방식은 이것이다:

v = v - ((v >> 1) & (T)~(T)0/3); // 임시

v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // 임시

v = (v + (v >> 4)) & (T)~(T)0/255*15; // 임시

c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // 세기

더 많은 정보를 얻으려면 비트 집합의 수를 세는 것에 대한 이안 아쉬다운(Ian Ashdown)의 멋진 뉴스 그룹 글(https://groups.google.com/groups?q=reverse+bits&num=100&hl=en&group=comp.graphics.algorithms&imgsafe=off&safe=off&rnum=2&ic=1&selm=4fulhm%248dn%40atlas.uniserve.com)을 참조하라(이는 또한 틈샛길 덧셈으로 알려져 있다.). 최선의 비트 세기 방법은 앤드류 샤피라(Andrew Shapira, http://onezero.org/)에 의해서 2005년 10월 5일에 보게 되었다: 그는 AMD 애슬론 64와 옵테론 프로세서에 대한 소프트웨어 최적화 가이드, Software Optimization Guide for AMD Athlon™ 64 and Opteron™ Processors(http://www.google.de/url?sa=t&rct=j&q=software%20optimization%20guide%20for%20amd%20athlon%E2%84%A2%2064%20and%20opteron%E2%84%A2%20processors&source=web&cd=1&cad=rja&ved=0CDUQFjAA&url=http%3A%2F%2Fsupport.amd.com%2Fde%2FProcessor_TechDocs%2F25112.PDF&ei=XT_wUID3KsXcswaovYGIAg&usg=AFQjCNEJAHRW8WlxaeBxGQgGqNTeXRkIFQ&bvm=bv.1357700187,d.Yms) 187-188 페이지에서 찾았다. 찰리 고든(Charlie Gordon)은 2005년 12월 14일에 완전 병렬 버전에서 한 개의 연산을 없앨 수 있는 방법을 제안했고, 돈 클러그스톤(Don Clugston)은 2005년 12월 30일에 세 개의 연산을 더 줄였다. 나는 Don의 제안을 옮기면서 오타를 냈고, 에릭 콜(Eric Cole)가 2006년 1월 8일에 이를 알려 줬다. 에릭(Eric)은 그 후 2006년 12월 17일에 최선의 방법에 대한 임의의 비트 길이 일반화를 제안했다. 2007년 4월 5일에, 알 윌리암스(Al William)는 첫째 방법의 윗 부분에 죽은 코드 한 줄을 가지고 있음을 발견했다.

저작자표시

Blue Frog's Wisdom

병렬 비트 카운팅(Parallel Bit Counting)

댓글

티스토리툴바

병렬 비트 카운팅(Parallel Bit Counting)

관련글

댓글

티스토리툴바