x86 question 
Author Message
 x86 question

I was wondering if any of you know a good, short way to count the number of
bits turned on in a qword.

Thanks in advance.



Tue, 20 Aug 2002 03:00:00 GMT  
 x86 question
I am not sure if this the best way to do this but.
Break up your qword into nibbles, and then just use
a lookup table of bit counts.
Have more questions, just ask.

* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!



Tue, 20 Aug 2002 03:00:00 GMT  
 x86 question
Thanks.  Good idea.


Tue, 20 Aug 2002 03:00:00 GMT  
 x86 question


Quote:
> I was wondering if any of you know a good, short way to count the number of
> bits turned on in a qword.

> Thanks in advance.

well if you're programming on a 386 or better, just call bt a bunch of
times, and incrementing another register each time that that the flag is
up.  I guess that's pretty fast.  What do you need if for?  There is
probably a better way, depending on the application.


Wed, 21 Aug 2002 03:00:00 GMT  
 x86 question

Quote:

> I am not sure if this the best way to do this but.
> Break up your qword into nibbles, and then just use
> a lookup table of bit counts.
> Have more questions, just ask.

Yes, breaking it into nibbles (or maybe bytes) and using a lookup table
makes sense to me too. If you are looking for a "smarter", yet probably less
efficient algorithm, split it up into two dwords and do the following :
(translation into asm left as exercise. The algorithm was found in K&R The C
programming language 2nd ed)

int count(unsigned x)
{
 int b=0;
 while(x!=0)
 {
  x&=x-1;
  b++;
 }
 return b;

Quote:
}



Wed, 21 Aug 2002 03:00:00 GMT  
 x86 question


Quote:
>I was wondering if any of you know a good, short way to count the number
>of bits turned on in a qword.

>Thanks in advance.

The easiest method I can think of, without using a lookup table, would be
to split it into two dwords, and then run the following code over each
one:

xor bx,bx
start:
shl eax,1
adc bx,0
cmp eax,0
jnz start

where eax contains the dword you are working on. HTH
--
Graham Cox

Remove antispam, you get the idea
ICQ# 24532124
PGP Public Thingy available upon request, or from keyserver.



Wed, 21 Aug 2002 03:00:00 GMT  
 x86 question

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



Wed, 21 Aug 2002 03:00:00 GMT  
 x86 question

Quote:
> I was wondering if any of you know a good, short way to count the
number of
> bits turned on in a qword.

You could pass this routine the 2 halves of the qword and add the
results.

;
======================================================================
======
; = In:         EAX     Register holding up to 32 "one" bits to be
counted
; = Out:        BL      Count of "one" bits that were in EAX
; = Trashes:;   EAX, ECX
;
======================================================================
======
BitCount proc
        sub bl,bl               ; Init count of ones.
        or eax,eax              ; Are there *any* ones?
        jz CountDone            ; Nope, we're done.
CountEm:
        bsf ecx,eax             ; ECX = [0, 1, .., 31]
        inc bl                  ; Count the bit.

;--------------------------------------------------------------------
        ; Two SHRs are needed for the special case of EAX=0x80000000.
        ; Otherwise, you could simply "inc cl" and "shr eax,cl".

;--------------------------------------------------------------------
        shr eax,cl              ; Move it to bit 0.
        shr eax,1               ; Move it out.
        jnz CountEm             ; If there are more ones, count them
too.
CountDone:
        ret
BitCount endp



Sun, 25 Aug 2002 03:00:00 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Q: porting x86 asm to Solaris v2.6 (SunOS 5.5.1) running on x86

2. Convert intel x86 to AT&T x86 asm source

3. Help! x86 optimization questions

4. Intel x86 Efficiency Question

5. beginnerish question (x86, stosw)

6. Another x86 intel->at&t porting question

7. Some x86 architecture questions.

8. Some x86 architecture questions.

9. beginnerish question (x86, stosw)

10. GCC/x86 assembly procedure Question

11. x86 DIV question

12. x86 DIV question

 

 
Powered by phpBB® Forum Software