Bits Count

[Aldo Vitagliano]

Hi all,

I am looking for an efficient method of getting the bits count of an integer class variable (i.e. how many bits in the variable are set "on").

So far I devised two ways, using just plain Basic code (I'm not familiar with Assembly language), and here is my benchmark code for both:

[FONT="Courier New"]
DEFLNG A-Z
FUNCTION PBMAIN () AS LONG
   REGISTER NBITS AS LONG, NUM AS LONG
   '#REGISTER NONE
   N=10000000 
   T!=TIMER
   FOR I=1 TO N
      NBITS=0: NUM=I
      DO UNTIL NUM=0
         NBITS=NBITS+(NUM AND 1)
         NUM=NUM\2
      LOOP
   NEXT
   PRINT USING$("####.#",TIMER-T!)
   T!=TIMER
   FOR I=1 TO N
      NBITS=0
      FOR NUM=0 TO 31
         NBITS=NBITS+BIT(I, NUM)
      NEXT
   NEXT
   PRINT USING$("####.#",TIMER-T!)
WAITKEY$
END FUNCTION    
 [/FONT]

The second method seems to be slightly faster than the 1st one.
Any suggestion for a better way ?

[Bob Zale]

DEFLNG A-Z
FUNCTION PBMAIN () AS LONG
   REGISTER NBITS AS LONG, NUM AS LONG
   N=10000000
   T!=TIMER
   FOR I=1 TO N
      NBITS=0: NUM=I
      DO UNTIL NUM=0
         NBITS=NBITS+(NUM AND 1)
         NUM=NUM\2
      LOOP
   NEXT

   PRINT USING$("####.#",TIMER-T!)
   T!=TIMER
   FOR I=1 TO N
      NBITS=0
      FOR NUM=0 TO 31
         NBITS=NBITS+BIT(I, NUM)
      NEXT
   NEXT
   PRINT USING$("####.#",TIMER-T!)

   T!=TIMER
   FOR I=1 TO N
      ASM   xor   eax, eax
      ASM   mov   ecx, I
            LOOPIT:
      ASM   shr   ecx, 1
      ASM   jz    ASMEXIT
      ASM   adc   eax, 0
      ASM   jmp   LOOPIT
            ASMEXIT:
      ASM   adc   eax, 0
      ASM   mov   NBITS, eax
   NEXT
   PRINT USING$("####.#",TIMER-T!)

WAITKEY$
END FUNCTION

[Paul Dixon]

Aldo,
it's called a "population count" and the Athlon optimisation manual shows one way to do it very quickly:

http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/22007.pdf

search for population count in the above document.

Paul.

PBWin9 program
#REGISTER NONE
FUNCTION PBMAIN AS LONG
'A fast way to count bits set in a 32 bit word
'from the AMD Athlon optimization manual

v&=&h1234510  'the word to count the bits in
retval&=0    'the answer

!MOV EAX,v&
!MOV EDX,EAX
!SHR EAX,1
!AND EAX,&h055555555
!SUB EDX,EAX
!MOV EAX,EDX
!SHR EDX,2
!AND EAX,&h033333333
!AND EDX,&h033333333
!ADD EAX,EDX
!MOV EDX,EAX
!SHR EAX,4
!ADD EAX,EDX
!AND EAX,&h00F0F0F0F
!IMUL EAX,&h01010101

!SHR EAX,24
!MOV retVal&,EAX

MSGBOX STR$( retval&)

END FUNCTION

[Aldo Vitagliano]

Thank you Bob and Paul for your replies.

Here are the results from the benchmark done with 100,000,000 iterations on my Intel Quad 2.4 GHz machine:

The two Basic methods:
1) 32 seconds
2) 27 seconds

Bob's ASM code:
3) 2.3 seconds (excellent!)

Paul's code:
4) 0.5 seconds (amazing!)

Thanks again!

[Paul Dixon]

Aldo,
if you need it really fast then follow the link I gave you and an alternative version using MMX is shown which is said to be twice as fast as the version I posted.

Paul.

[John Gleason]

If you're not too familiar with asm and don't mind making a little array at the start of your program, here is a way using basic code PEEK that is nearly as fast. Indexed pointers with the array would be another fast way too.

DEFLNG A-Z

FUNCTION PBMAIN () AS LONG
   REGISTER NBITS AS LONG, NUM AS LONG
   LOCAL iPtr AS LONG
   DIM bitCount(255) AS STATIC LONG
   FOR ii = 0 TO 255
      bitCount(ii) = TALLY(BIN$(ii), "1")
   NEXT

   N=100000000
   T!=TIMER
   FOR I=1 TO N
      ASM   xor   eax, eax
      ASM   mov   ecx, I
            LOOPIT:
      ASM   shr   ecx, 1
      ASM   jz    ASMEXIT
      ASM   adc   eax, 0
      ASM   jmp   LOOPIT
            ASMEXIT:
      ASM   adc   eax, 0
      ASM   mov   NBITS, eax
   NEXT
   PRINT USING$("####.###",TIMER-T!)

   T!=TIMER
   FOR I=1 TO N
      !MOV EAX,I
      !MOV EDX,EAX
      !SHR EAX,1
      !AND EAX,&h055555555
      !SUB EDX,EAX
      !MOV EAX,EDX
      !SHR EDX,2
      !AND EAX,&h033333333
      !AND EDX,&h033333333
      !ADD EAX,EDX
      !MOV EDX,EAX
      !SHR EAX,4
      !ADD EAX,EDX
      !AND EAX,&h00F0F0F0F
      !IMUL EAX,&h01010101

      !SHR EAX,24
      !MOV NBITS,EAX
   NEXT
   PRINT USING$("####.###",TIMER-T!)

   T!=TIMER
   iPtr = VARPTR(I)
   FOR I=1 TO N
      NBITS = 0
      NBITS =  bitCount(PEEK(BYTE, iPtr))
      NBITS += bitCount(PEEK(BYTE, iPtr + 1))
      NBITS += bitCount(PEEK(BYTE, iPtr + 2))
      NBITS += bitCount(PEEK(BYTE, iPtr + 3))
   NEXT
   PRINT USING$("####.###",TIMER-T!)

   WAITKEY$

END FUNCTION