Jump to content
Karl G

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.

  • Like 2

Share this post


Link to post
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.

  • Like 3
  • Thanks 1

Share this post


Link to post
Share on other sites
Posted (edited)
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
  • Like 3

Share this post


Link to post
Share on other sites
Posted (edited)

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
  • Like 2

Share this post


Link to post
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.

  • Like 3

Share this post


Link to post
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.

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.

Share this post


Link to post
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
	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

 

 

 

  • Like 1

Share this post


Link to post
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...