Announcement

Collapse
No announcement yet.

Bits Count

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

  • John Gleason
    replied
    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, 09:09 PM. Reason: 1st += changed to just =

    Leave a comment:


  • Paul Dixon
    replied
    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.

    Leave a comment:


  • Aldo Vitagliano
    replied
    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!

    Leave a comment:


  • Paul Dixon
    replied
    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

    Leave a comment:


  • Bob Zale
    replied
    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

    Leave a comment:


  • Aldo Vitagliano
    started a topic Bits Count

    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:
    [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 ?
Working...
X