Counting bits in a byte

[+Karl G]

This is spawned from a discussion in the batari Basic forum about how to count the number of bits that differ between two bytes. The first part is easy: do an EOR of the two bytes to get a result containing 1s where the bits differed between the two bytes. So from there the question becomes how to count the number of 1s in a byte. I came up with 3 different possibilities.

 

1) Iterate. Check the rightmost bit, increment a counter if it is 1, then lsr. Repeat until number is zero

2) Big table: Have a 256-byte lookup table returning the number of 1 bits for all 256 values of the byte being checked.

3) Hybrid: Load the byte to be checked, and #$0F, and check a 16-byte lookup table to see how many 1s are in that nybble. Load the byte again, do lsr 4 times, and check the lookup table again. Add the two results.

 

I just wanted to see if anyone had a more clever way to get the number of 1 bits in a byte.

[JetSetIlly]

Simplest method other than (1) I know which is easy to remember. First published in 1960 https://dl.acm.org/doi/abs/10.1145/367415.367425

bitCount = 0
while val != 0
	val &= val - 1
	bitCount++
}

Nice thing about this is that if there is only one bit set then the loop iterates once. If two bits are set then it iterates twice, etc.

[+Karl G]

11 hours ago, JetSetIlly said:

Simplest method other than (1) I know which is easy to remember. First published in 1960

 

Excellent! I love that it is a 62 year old solution as well.  Here's my translation into 6502 assembly. Byte to be checked is temp1, and X will contain number of bits. No doubt others could optimize further:

    ldx #0
    sec
CountBitsLoop
    lda temp1
    beq ____done_count_bits
    inx
    sbc #1
    and temp1
    sta temp1
    jmp CountBitsLoop

 

Edited May 9, 2022 by Karl G

[Danjovic]

Full solution:

lda byte1

eor byte2

sta temp

lda #0

ldy #8

loop: rol temp

adc #0 ; a = a + 0 + carry 

dey

bne loop

 

at the end a holds bit count.

 

 

 

 

 

 

 

 

 

Edited May 9, 2022 by Danjovic

[+Al_Nafuur]

?

 

No 6502 ASM solution on rosettacode:
https://rosettacode.org/wiki/Population_count

 

 

[orange808]

Could we abuse ASR for this?

 

https://atariage.com/forums/topic/124320-illegal-opcodes/

[Omegamatrix]

On 5/8/2022 at 4:45 PM, Karl G said:

This is spawned from a discussion in the batari Basic forum about how to count the number of bits that differ between two bytes. The first part is easy: do an EOR of the two bytes to get a result containing 1s where the bits differed between the two bytes. So from there the question becomes how to count the number of 1s in a byte. I came up with 3 different possibilities.

 

1) Iterate. Check the rightmost bit, increment a counter if it is 1, then lsr. Repeat until number is zero

2) Big table: Have a 256-byte lookup table returning the number of 1 bits for all 256 values of the byte being checked.

3) Hybrid: Load the byte to be checked, and #$0F, and check a 16-byte lookup table to see how many 1s are in that nybble. Load the byte again, do lsr 4 times, and check the lookup table again. Add the two results.

 

I just wanted to see if anyone had a more clever way to get the number of 1 bits in a byte.

No, I think that is pretty much it unless there is some weird not obvious method.

 

Here's what I would do:

    ldx    #$FF          ; use TSX if SP=$FF to save a byte
.doInx:
    inx
.doShift:
    lsr
    bcs    .doInx
    bne    .doShift      ; will exit early if no more bits are set

;X = number of bits, A = 0, carry is clear

You might want to choose ASL instead of LSR depending on what it is known about the data beforehand. I.e. if bit 0 is always clear but bit 7 is unknown then ASL makes more sense to use.

[stepho]

The algorithm by JetSetIlly is known as Brian Kernighan's method, although it didn't originate with him - he just popularised it.

 

There is one remaining method. Go to this webpage and then scroll down to the parallel method.

https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Use the best method for 32-bits - you will have to cut it down to 8 bits (do the 0x55, 0x33, 0x0f steps as 8-bit but skip the 0x01 and final >>24 steps).
It has a lot of shifts and adds, so not sure if it will be quicker than the methods above.

 

That web page is also a great grab bag of tricks - although they are mostly optimisations for bigger CPU's than ours.

[+Andrew Davie]

12 hours ago, Karl G said:

 

Excellent! I love that it is a 62 year old solution as well.  Here's my translation into 6502 assembly. Byte to be checked is temp1, and X will contain number of bits. No doubt others could optimize further:

 

 

I count that at about 18 cycles/bit.

This one is about 13 cycles/bit...  still expensive.  I'd use a 16-byte table lookup myself.

Would be 6 cycles with 0 bits set, and 115 cycles with 8 bits set.

16 bytes of ROM.

; assume A = value to count bits for and it's just been loaded

	 beq doneCount

         ldx #0
         sec
count    inx
	 sta temp
	 sbc #1
         and temp
	 bne count
	 txa

doneCount
; a = # bits
        rts

 

table lookup...  untested.

Looks like 38 cycles always...  that's averaging 9 cycles/bit I think.

forgot the cycle count for abs,x and abs,y so I used 5.

36 bytes of ROM.

countBits

 ; A = byte to count bits of

        sta temp
        and #15
        tax
	lda temp
	lsr
	lsr
	lsr
	lsr
	tay

	clc
	lda t16,x
	adc t16,y

; #bits in A
        rts

t16
 dc 0 ; 0000
 dc 1 ; 0001
 dc 1 ; 0010
 dc 2 ; 0011
 dc 1 ; 0100
 dc 2 ; 0101
 dc 2 ; 0110
 dc 3 ; 0111
 dc 1 ; 1000
 dc 2 ; 1001
 dc 2 ; 1010
 dc 3 ; 1011
 dc 2 ; 1100
 dc 3 ; 1101
 dc 3 ; 1110
 dc 4 ; 1111