1. 켜진 비트 수 세기

비트 수를 센다는 건 보통 "on bit의 개수를 가져온다." 즉 pop count로 주로쓰이는 용어입니다.
대부분의 프로세서가 popcnt 옵코드를 제공해 빠르게 계산할 수 있죠

가령 0x5f3759df는 이진수로 0101 1111 0011 0111 0101 1001 1101 1111 이므로 popcount값은 2+4+2+3+2+2+3+4=22가 되겠죠


이것을 계산하는 전통적인 방법은 분할정복으로 2,4,8,16,32bit field 씩 나누어 계산하는 방법이 있습니다.

크기가 작은 2,4필드로 계산하는 예를 들어보면

0110 -> 01 01 -> 00 10 이 됩니다.

이는 x = (x & 0x5) + ((x >> 1) & 0x5); 라는 짧은 코드로 계산될 수 있죠.

이 방법엔 이산수학에서 배우는 해밍 거리의 응용인 해밍 무게(Hamming weight)란 이름이 붙어있죠.


32bit의 직관적인 구현은 다음과 같습니다.

x = (x & 0x55555555) + ((x >>  1) & 0x55555555) // 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01

x = (x & 0x33333333) + ((x >>  2) & 0x33333333) // 0011 0011 0011 0011 0011 0011 0011 0011

x = (x & 0x0F0F0F0F) + ((x >>  4) & 0x0F0F0F0F) // 00001111 00001111 00001111 0000111

x = (x & 0x00FF00FF) + ((x >>  8) & 0x00FF00FF) // 0000000011111111 0000000011111111

x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF) // 00000000000000001111111111111111

이제 한 줄씩 줄여볼게요


먼저 첫 번째 배정문은 

x = x - ((x >> 1) & 0x55555555) 로 줄여질 수 있습니다. 잘 생각해보면 1bit보다 상위비트가 켜져있으면 빼도 msb가 바뀔 이유가 없고, 오직 두 자리 수의 이진수 이기에 가능한 연산입니다.

두 번째 배정문은 줄일 여유는 없어보이니 일단 넘깁시다.

세 번째 배정문은

x = (x + (x >> 4)) & 0x0F0F0F0F 로 줄일 수 있습니다. 첫 번째 배정문은 아직 비트 정렬이 되어있지 않은 상태였기에 덧셈연산은 치명적일 수 있었지만,

세번째 연산에선 8bit field에서 상위 4bit가 0000이기 때문에 축약될 수 있는 거죠

네 번째 배정문도 같은 연산으로

x = x + (x >> 8)

다섯 번째 배정문도 같은 연산으로

x = x + (x >> 16)

으로 줄 일 수 있습니다. 단, 상위 16비트와 16비트 하위 비트필드의 상위 8bit가 남고 덧셈연산으로 8bit자리가 변할 수 있으므로 

x = x & 0x0000003F 연산을 취해야 합니다.

또 네 번재 배정문과 다섯 번째 배정문은

x = (x * 0x01010101)>>28

로도 줄일 수 있습니다. 이 연산은 x + (x << 8) + (x << 16) + (x << 32)를 연산해 상위 8bit를 가져옵니다. 즉 mod 15연산이죠


그럼 두 번째 배정문은 어떻게 줄여야될까요?

간단한 아이디어는 곱셈을 이용하는 방법이 있습니다.

x = x - 3 * ((x >> 2) & 0x33333333)

이 방법은 첫 번째 배정문에서 2bit field들이 00 01 10의 값만 가진 것과 감산연산을 응용한 것입니다. 

하지만 이 방법은 연산시간이 원래 것보다 길 뿐더러 연산횟수도 같죠.


3bit filed를 이용해 계산한 방법도 있습니다.

각 3bit filed의 켜진 비트 수를 담는 아이디어입니다.

인접한 2bit filed들을 더해 6bit filed합을 만들고, mod 63연산을 실행시킴으로써 그 6bit filed의 합을 구하는 방법입니다.

6bit는 0011 1111 => 0x3F => 63이니깐요


긴 숫자들은 모두 8진수들 입니다.

// 각 3bit field의 켜진 비트수를 센다.

n = (x >> 1) & 033333333333 => 11011011011011011011011011011011 

x = x - n

n = (n >> 1) & 033333333333 => 11011011011011011011011011011011

x = x - n

// 6bit field의 합들

x = (x + (x >> 3)) & 030707070707 => 11000111000111000111000111000111

x = x % 63

마지막 배정문은 x = ((x * 0404040404) >> 26) + (x >> 30)으로 대체할 수 있습니다. => 100000100000100000100000100


포함된 켜진 비트가 작다고 확신할 수 있는 경우엔 다음과 같은 방법도 사용할 수 있어요

n = 0

while ( x )

   n++, x = x & (x - 1)

n이 반환값이 됩니다.


공간적 여유가 있다면 다음과 같은 방법도 있습니다.

static uint8_t table[256] = 

       {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 

4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };

table[x & 0xff] + table[(x >> 8) & 0xff] + table[(x >> 16) & 0xff] + table[(x >> 24)]


넘쳐난다면 65535개를 써도 되죠

다음은 vb.net에서 추출하는 소스입니다.

    Public Function count_bit(ByVal a As UInt32)

        Dim j = 0

        Do

            j += a And 1

            a >>= 1

        Loop While a

        Return j

    End Function


        Dim a As New StringBuilder

        a.Append(vbTab)

        For i As Integer = 0 To &HFFFF

            a.Append("0x" & Hex(count_bit(i)) & ", ")

            If i Mod 16 = 15 Then

                a.Append(vbCrLf & vbTab)

            End If

        Next

        RichTextBox1.Text = a.ToString


popcnt(x) + popcnt(y)는 처음 두 배정문은 각각 연산한뒤 세 번째 단계부터 두 연산값을 더해 처리하면 실행시간을 줄일 수 있습니다.

popcnt(x) - popcnt(y)는 약간의 계산과정 단축으로 만들 수 있습니다.

x = x - ((x >> 1) & 0x55555555)

x = (x & 0x33333333) + ((x >> 2) & 0x33333333)

y = ~y

y = y - ((y >> 1) & 0x55555555)

y = (y & 0x33333333) + ((y >> 2) & 0x33333333)

x = x + y

x = (x & 0x0F0F0F0F) + ((x >>  4) & 0x0F0F0F0F)

x = x + (x >> 8)

x = x + (x >> 16)

x = (x & 0x0000007F) - 32

이는 popcnt(x) + popcnt(~y) - 32 연산과 같습니다.

y = ~y부분을 없애고  - 32를 지우면 덧셈함수가 되는 거죠


다음은 popcnt(x) == popcnt(y)이면 0을,popcnt(x) > popcnt(y)면 1을 돌려주는 함수입니다.

input xp, yp

x = xp & ~yp (~(xp ^ yp))

y = yp & ~xp

whlie ( 1 )

   if ( x == 0 ) return y | -y

   if ( y =  0 ) return 1

   x = x & (x - 1) // 비트가지고 놀기 기초 게시글 참조

   y = y & (y - 1)




2. 배열에서 1비트 개수 세기

이 알고리즘은 자리올림수 가산기(CSA)를 이용한 방법입니다.

https://en.wikipedia.org/wiki/Carry-save_adder (한국어로도 있으나 설명이 부족하네요)


구현은 다음과 같습니다.

#define CSA(h,l, a,b,c) \

{ unsigned u = a ^ b; unsigned v = c; h = (a & b) | (u & v); l = u ^ v; }


int popcntArray(unsigned a[], int n)

   int tot, i

   unsigned ones, twos

   tot = 0, ones = 0

   for ( i = 0; i <= n - 2; i += 2 )

        CSA(twos, ones, ones, a[i], a[i+1])

        tot = tot + popcnt(twos)

   tot = (tot << 1) + popcnt(ones)

   if ( n& 1 )

      tot = tot + popcnt(a[i])

   return tot


CSA에 관해선 처음듣네요

소스만 올려놓고 가겠습니다. 저도 몰라요 안배워서