Quote:

>I was wondering if any of you know a good, short way to count the number of

>bits turned on in a qword.

I recall a shift/and/add algorithm, where you divide a word into smaller

groups of bits and add them. Similar to MMX instructions:

- look at a word of n bits as n 1-bit values

- use 'mov', 'and' and 'shr' to split the word into two words of n/2 2-bit

values

- add them up

- repeat for n/2 2-bit -> n/4 4-bit n/8 8-bit, etc...

In pseudo code for 16-bit word (w):

w := (w AND 5555h) + ((w AND AAAAh) shr 1)

w := (w AND 3333h) + ((w AND CCCCh) shr 2)

w := (w AND 0F0Fh) + ((w AND F0F0h) shr 4)

w := (w AND 00FFh) + ((w AND FF00h) shr 8)

For implementation, we probably can save a 'bit' or two

here and there, because we only need a certain number

of bits for the counts. E.g. for 16-bit, we only need a 5-bit

counter. For 64 bits, we need an 7-bit counter.

For a quadword in x86 (edx:eax, untested!!):

; First

mov ecx,edx

mov ebx,eax

and edx,55555555h

and ecx,0AAAAAAAAh

shr ecx,1

and eax,55555555h

and ebx,0AAAAAAAAh

shr ebx,1

add edx,ecx

add eax,ebx

; Second

mov ecx,edx

mov ebx,eax

and edx,33333333h

and ecx,0CCCCCCCCh

shr ecx,2

and eax,33333333h

and ebx,0CCCCCCCCh

shr ebx,2

add edx,ecx

add eax,ebx

; Now we have 4-bit counters, each for only 4 bits while a 4-bit

; counter can add up to 15, which includes 8 when I add eax and edx...

add eax,edx

; Third

mov ebx,eax

and eax,0F0F0F0Fh

and ebx,0F0F0F0F0h

shr ebx,4

add eax,ebx

; Fourth

mov ebx,eax

and eax,0FF00FFh

and ebx,0FF00FF00h

shr ebx,8

add eax,ebx

; Fifth

mov ebx,eax

and eax,0FFFFh

shr ebx,16

add eax,ebx

So that is: 7 'mov', 13 'and', 7 'shr' and 8 'add' = 35 instructions.

H