rep movsd

부호 없는 32비트 정수에서 1로 세트된 비트의 수를 세어서 돌려준다. 예컨대, 15를 받으면, 4개의 비트가 세트되어 있으니 4를 돌려준다.

누가 갑자기 와서 이 함수를 당장 만들어내라고 하면 제일 먼저 생각해낼 만한 것은 LSB가 1이면 1을 더하고 오른쪽으로 쉬프트를 하는 루프를 떠올릴 것이다. 다른 방법으로는 1바이트 안의 비트 수를 적어 놓은 테이블을 만들어 놓고 4번 루프를 돌면서 각 바이트 안의 비트 수를 더하는 방법도 있다.

그런데, 메모리 접근하는데 시간이 오래 걸리고, 루프를 32번 도는 것도 참을 수 없이 느리다면, 이런 방법이 있다: 1비트로 표현한 2진수를 더하면 그 최대값은 2비트로 표현이 가능하다는 것에 주목하면 이 원리를 쉽게 이해할 수 있다. 즉, 맨 처음에는 홀수번째 비트와 짝수번째 비트를 쪼개서 더한다. 그 다음에는 2비트 묶음 단위로 더하고, 그 다음에는 니블 단위로, 바이트 단위로, 16비트 단위로 더해주면 원하는 답이 나온다. 이 원리를 인텔 32비트 어셈블리어로 직역하면 다음과 같다.

; unsigned bitcount(uint32_t a)
bitcount PROC
        mov     eax,[esp+4]
        ; 비트 단위 더하기
        mov     edx,eax
        and     eax,55555555h  ; 홀수 비트
        xor     edx,eax        ; 짝수 비트
        shr     edx,1          ; 짝수 비트를 하나 밀어서
        add     eax,edx        ; 더해주면 16개의 부분합이 나온다.
        ; 2비트 단위 더하기
        mov     edx,eax
        and     eax,33333333h
        xor     edx,eax
        shr     edx,2
        add     eax,edx
        ; 니블 단위 더하기
        mov     edx,eax
        and     eax,0f0f0f0fh
        xor     edx,eax
        shr     edx,4
        add     eax,edx
        ; 바이트 단위 더하기
        mov     edx,eax
        and     eax,00ff00ffh
        xor     edx,eax
        shr     edx,8
        add     eax,edx
        ; 16비트 단위 더하기
        mov     edx,eax
        and     eax,0000ffffh
        xor     edx,eax
        shr     edx,16
        add     eax,edx
        ret
bitcount ENDP

그런데, 이 코드를 유심히 살펴보면 이렇게 많이 쓸 필요가 없다는 것을 곧 알게 된다. 불필요한 부분을 제거하고 좀더 간결하게 짜면 다음과 같다.

; unsigned bitcount(uint32_t a)
bitcount PROC
        mov     eax,[esp+4]
        mov     edx,eax
        shr     eax,1
        and     eax,55555555h
        sub     edx,eax
        mov     ecx,33333333h
        mov     eax,edx
        shr     edx,2
        and     eax,ecx
        and     edx,ecx
        add     eax,edx
        mov     edx,eax
        shr     eax,4
        add     eax,edx
        and     eax,0f0f0f0fh
        imul    eax,01010101h
        shr     eax,24
        ret
bitcount ENDP

이 함수가 사용되는 경우: 작은 클래스의 객체들을 많이 생성하여 new를 스스로 만들어 쓰는 경우, 불필요한 낭비를 줄이기 위해 블록 헤더를 따로 두지 않고 사용중인 메모리 블록을 비트맵으로 관리한다. 이럴때, 객체를 몇개나 생성했는지를 알려면 비트맵의 비트의 수를 세면 된다.

똑같은 원리가 파일시스템에도 사용된다. 파일저장블록(FAT용어로는 클러스터)의 비트맵을 이용해서 사용된 블록을 기록하고 관리하는 파일시스템에서 디스크 사용량을 알려고 한다면, 같은 방식으로 빠르게 알 수 있다. (NTFS가 이런 방식을 쓴다는 얘기를 들었다. 소스코드를 본 적이 없어서 정말인지는 모른다.)