(Solved) Is there a better way to count bits?

[m8si]

I need to know how many of the bits are set in a byte. 0001 = 1, 0010 = 1, 0011 = 2 etc...

I came up this solution but I feel there got to be a better way.

LDX #%1111 ;Count set bits of X
TXA
LSR
LSR
LSR
STA temp

TXA
AND #%0100
LSR
LSR
ADC temp
STA temp

TXA
AND #%0010
LSR
ADC temp
STA temp

TXA
AND #%0001
ADC temp
STA temp ; temp is now #4

 

[JamesNES]

That's fun, I hadn't thought of doing something like that before so I had to give it a go. I came up with this:

LDA #$00
STA temp
LDA yourByte   ;;byte to count the bits of

LDX #$08
-countLoop
    ROL
    BCC +
        INC temp
    +
    DEX 
    BNE -countLoop

temp ends up with the amount of bits in it.

 

[m8si]

Cool! So that's basically the same thing but inside a loop? Seems more efficient approach. Thank you!

 

[JamesNES]

ROL shifts everything left but puts the top bit into the carry flag, so it does that 8 times and counts how many times the carry is set. Simplest way I could come up with anyway.

 

[m8si]

Nice. That's clever use of the carry flag. I feel I'm learning a lot from you every time I post a question.

 

[TakuikaNinja]

I'm bored and I think I figured out a better way. Here's my attempt, formatted as a macro:

MACRO CountBits arg0
    ;arg0 = byte to count bits of (should be an address)
LDA arg0
STA temp
BEQ +                 ; already 0? we know 0 bits are set, so skip
LDX #$08
LDA #$00              ; init bit counter
-
    ASL temp          ; shift left to put bit 7 into carry (and 0 into bit 0)
    ADC #$00          ; add carry to counter (0 = not set, 1 = set)
    DEX
    BNE -
    STA temp          ; store result in temp (optional)
+
ENDM

This hinges on the fact that ADC #$00 adds the carry flag to A. The result is conveniently left in A once it finishes. X will be cleared to 0 if the value is > 0. This runs in constant time, by the way (ignoring the check for a 0 value at the start).

 

[TakuikaNinja]

Here is an alternate solution based on Brian Kernighan’s Algorithm:

MACRO CountBits arg0
    ;arg0 = byte to count bits of (should be an address)
LDA arg0
BEQ +                ; already 0? we know 0 bits are set, so skip
LDX #$00             ; otherwise init bit counter
-
    INX              ; increment bit counter
    STA temp
    DEC temp
    AND temp         ; A &= (A-1)
    BNE -            ; loop will terminate once A == 0
    TXA              ; copy result to A
+
STA temp             ; store result into temp (optional)
ENDM

A contains the result when it finishes. X will be overwritten with the result if the value is > 0. The main difference is that the number of times the looped portion runs is exactly the number of bits set. Pretty neat, isn't it?

 

[m8si]

Wow. That looks very neat. I guess the last one is also the most efficient one. Thank you!

 

[m8si]

Had the time to test out the code and it works perfectly. In case someone is interested how is this code going to be used here is one possible use case for it:

The Myth of Zayla

The Myth of Zayla Started as a ByteOff III entry, but as always I got a bit carried away and now I am going to develop and release a full game in 2023. There will be many bugs to tackle and things to be done for sure. But having this awesome community supporting I believe it will be possible...

www.nesmakers.com

 

[JamesNES]

Whoa those are both really slick! Always wondered what ADC #$00 could be used for.

 

[TakuikaNinja]

I have been informed today that there some better alternatives in this 6502 dot org thread: http://forum.6502.org/viewtopic.php?t=1206
The smallest of which looks like this, in subroutine form:

;======================================================
; Bit Counting Using Shifts
;------------------------------------------------------
; The smallest method for count bits shifts the value
; left one bit at a time and counts each one bit that
; is shifted out.
;
; If we use ASL to perform the shift then the value
; will become zero after at most eight iterations. By
; looking for see when the value has reached zero we
; can stop iterating as soon as there are no bits left
; to shift out.
;
; Time: 18 to 76 cycles (depending on the value)
; Size: 10 bytes

BitCountIterative:
        LDX #$FF                ; Set count to -1
.Incr:  INX                     ; Add one to count
.Loop:  ASL                     ; Shift by one bit
        BCS .Incr               ; Count one bits
        BNE .Loop               ; Repeat till zero
        TXA                     ; Move count to A
        RTS