Announcement

Collapse
No announcement yet.

Bits Count

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Bits Count

    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:
    Code:
    
    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    
     
    The second method seems to be slightly faster than the 1st one.
    Any suggestion for a better way ?
    Aldo Vitagliano
    alvitagl at unina it

  • #2
    Code:
    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

    Comment


    • #3
      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/cont...docs/22007.pdf
      search for population count in the above document.

      Paul.
      Code:
      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

      Comment


      • #4
        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!
        Aldo Vitagliano
        alvitagl at unina it

        Comment


        • #5
          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.

          Comment


          • #6
            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.
            Code:
            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
            Last edited by John Gleason; 19 Oct 2009, 10:09 PM. Reason: 1st += changed to just =

            Comment

            Working...
            X