IGNORED

# Counting bits in a byte

## Recommended Posts

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.

##### Share on other sites

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.

• 3
• 1
##### Share on other sites

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 by Karl G
##### Share on other sites

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 by Danjovic
##### Share on other sites

?

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

##### Share on other sites

Could we abuse ASR for this?

##### Share on other sites

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.

##### Share on other sites

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.

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.

##### Share on other sites

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

; #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
```

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.