Counting Number of Bits Set - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Counting Number of Bits Set

BretBret Posts: 114Member
I'm working on a program where I need to count the number of bits that are set in a Word (AX) or DWord (EAX). Below is the code I'm using now. I'm just wondering if there is some special CPU instruction(s) to do something like this, instead of needing to do a loop. It seems like there should be, but I don't know what it is. Any help would be appreciated. Thanks.

[code]
;--------------------------------------------------------------
;COUNT THE TOTAL NUMBER OF BITS THAT ARE SET IN A WORD OR DWORD
;Inputs: AX/EAX = Word/DWord to Test
;Outputs: CL = Number of Bits set in the Word/Dword
; ZF = Set if CL = 0
; = Clear if CL != 0
;Changes:
;--------------------------------------------------------------
CountAXBitsSet:
PUSH EAX ;Save used registers
AND EAX,0000_FFFFh ;Get rid of high word
CALL CountEAXBitsSet ;Count the bits
POP EAX ;Restore used registers
RET

CountEAXBitsSet:
PUSH BX ;Save used registers
XOR CL,CL ;Start counter at 0
MOV BL,32 ;Need to test 32 bits
S10: ;Loop to here for each bit
ROL EAX,1 ;High bit set?
JNC >S30 ;If not, keep testing
INC CL ;If so, increment the bit set counter
S30: ;Counter incremented, if appropriate
DEC BL ;Decrement loop counter
JNZ S10 ;If not done yet, keep testing
OR CL,CL ;Set return flag
POP BX ;Restore used registers
RET
[/code]

Comments

  • jeffleydajeffleyda Posts: 390Member
    here's a thing from the assembly gems page:

    http://www.df.lth.se/~john_e/fr_gems.html
    edit: (whoops, this link doesn't work directly, but it's the "Population count of a 32-bit register" link from that page)


    it makes my head hurt looking at it, but it is pretty short, and probably very fast.

    I recently wrote something to do that too:

    [code]
    ; countBits - count the number of bits set to 1
    ; input eax = bitmask
    ; output cx = value
    countBits proc
    xor cx, cx
    again:
    cmp eax, 0
    jz exit
    test eax, 1 ;BIT0
    jz nocount
    inc cx
    nocount:
    shr eax, 1
    jmp again
    exit:
    ret
    countBits endp
    [/code]

    totally unoptimized and dirty, but appeared to work.
    this at least doesn't have to go through the entire 32bits if the upper bits are already 0. As soon as it sees the last 1 bit, it bails out.

    -jeff!

    : I'm working on a program where I need to count the number of bits
    : that are set in a Word (AX) or DWord (EAX). Below is the code I'm
    : using now. I'm just wondering if there is some special CPU
    : instruction(s) to do something like this, instead of needing to do a
    : loop. It seems like there should be, but I don't know what it is.
    : Any help would be appreciated. Thanks.
    :
    : [code]:
    : ;--------------------------------------------------------------
    : ;COUNT THE TOTAL NUMBER OF BITS THAT ARE SET IN A WORD OR DWORD
    : ;Inputs: AX/EAX = Word/DWord to Test
    : ;Outputs: CL = Number of Bits set in the Word/Dword
    : ; ZF = Set if CL = 0
    : ; = Clear if CL != 0
    : ;Changes:
    : ;--------------------------------------------------------------
    : CountAXBitsSet:
    : PUSH EAX ;Save used registers
    : AND EAX,0000_FFFFh ;Get rid of high word
    : CALL CountEAXBitsSet ;Count the bits
    : POP EAX ;Restore used registers
    : RET
    :
    : CountEAXBitsSet:
    : PUSH BX ;Save used registers
    : XOR CL,CL ;Start counter at 0
    : MOV BL,32 ;Need to test 32 bits
    : S10: ;Loop to here for each bit
    : ROL EAX,1 ;High bit set?
    : JNC >S30 ;If not, keep testing
    : INC CL ;If so, increment the bit set counter
    : S30: ;Counter incremented, if appropriate
    : DEC BL ;Decrement loop counter
    : JNZ S10 ;If not done yet, keep testing
    : OR CL,CL ;Set return flag
    : POP BX ;Restore used registers
    : RET
    : [/code]:
  • BitByBit_ThorBitByBit_Thor Posts: 2,444Member
    : totally unoptimized and dirty, but appeared to work.
    : this at least doesn't have to go through the entire 32bits if the
    : upper bits are already 0. As soon as it sees the last 1 bit, it
    : bails out.
    :

    Using ADC *might* be faster than the jmp's. Don't know for sure though.

    Best Regards,
    Richard

    The way I see it... Well, it's all pretty blurry
  • BretBret Posts: 114Member
    : : totally unoptimized and dirty, but appeared to work.
    : : this at least doesn't have to go through the entire 32bits if the
    : : upper bits are already 0. As soon as it sees the last 1 bit, it
    : : bails out.
    : :
    :
    : Using ADC *might* be faster than the jmp's. Don't know for sure
    : though.
    :
    : Best Regards,
    : Richard
    :
    : The way I see it... Well, it's all pretty blurry

    Both possibly helpful tips (exiting the loop early and using ADC). The link is interesting as well (very tricky). I'm not sure how the code at the link would perform compared to an exit-early loop, though (depending on the exact bit pattern, of course). Also, as a rule I care more about size than I do speed, and the code on the link is quite long.

    I was thinking there might be a way to use some combination of XOR/SHx/ROx, or BCD conversion instructions (AAD/AAM/DAA/DAS), or LEA, or some other "trick" that I haven't thought of, to do it. Even if the "trick" only worked on a nibble or a byte at a time, it could reduce the number of times through the loop. The code at the link is sort of what I was thinking of (it breaks things up into small pieces and then puts them back together again), but I was hoping for something smaller in size.

    Thanks for the ideas.
  • BretBret Posts: 114Member
    : : : totally unoptimized and dirty, but appeared to work.
    : : : this at least doesn't have to go through the entire 32bits if the
    : : : upper bits are already 0. As soon as it sees the last 1 bit, it
    : : : bails out.
    : : :
    : :
    : : Using ADC *might* be faster than the jmp's. Don't know for sure
    : : though.
    : :
    : : Best Regards,
    : : Richard
    : :
    : : The way I see it... Well, it's all pretty blurry
    :
    : Both possibly helpful tips (exiting the loop early and using ADC).
    : The link is interesting as well (very tricky). I'm not sure how the
    : code at the link would perform compared to an exit-early loop,
    : though (depending on the exact bit pattern, of course). Also, as a
    : rule I care more about size than I do speed, and the code on the
    : link is quite long.
    :
    : I was thinking there might be a way to use some combination of
    : XOR/SHx/ROx, or BCD conversion instructions (AAD/AAM/DAA/DAS), or
    : LEA, or some other "trick" that I haven't thought of, to do it.
    : Even if the "trick" only worked on a nibble or a byte at a time, it
    : could reduce the number of times through the loop. The code at the
    : link is sort of what I was thinking of (it breaks things up into
    : small pieces and then puts them back together again), but I was
    : hoping for something smaller in size.
    :
    : Thanks for the ideas.

    I did a little more searching, and found a piece of C code that helped me figure out a good way to do it:

    [code]
    // v = Variable to Test
    // c = # of bits set in v
    for (c = 0; v ; c++)
    v &= (v-1);
    [/code]
    The number of times it does the loop is proportional to the number of bits set. Here the ASM code I "translated" this into:

    [code]
    ;--------------------------------------------------------------
    ;COUNT THE TOTAL NUMBER OF BITS THAT ARE SET IN A DWORD
    ;Inputs: EAX = DWord to Test
    ;Outputs: CL = Number of Bits set in the Dword
    ; ZF = Set if CL = 0
    ; = Clear if CL != 0
    ;Changes:
    ;--------------------------------------------------------------
    CountEAXBitsSet:
    PUSH EAX,EBX ;Save used registers
    XOR CL,CL ;Initialize Counter
    OR EAX,EAX ;Are there any bits set?
    JZ >S90 ;If not, we're done
    S10: ;Loop to here for each bits set
    INC CL ;Increment Bit Counter
    MOV EBX,EAX ;Subtract 1 from the
    DEC EBX ; current value
    AND EAX,EBX ;Mask out the smallest set bit
    JNZ S10 ;If there are still bits set, keep going
    S90: ;Done
    OR CL,CL ;Set return flag
    POP EBX,EAX ;Restore used registers
    RET
    [/code]
Sign In or Register to comment.