Here are four different ways to count the number of "ones" in an 8-bit binary number:

RR_bitcount - Shifts the byte and checks the carry. It's relatively slow.

TC_bitcount - Test and Count. Tests each bit individually. A very efficient approach is possible with the PIC's BTFSS (Bit Test File register, Skip if Set) instruction. Execution time is constant and the byte being tested is not affected.

bitcount - Uses a boolean relationship to clear the least significant bit that is set.

look_up_bits - Look up table approach. Not as fast as TC method and takes up more memory. You probably don't want to waste your time with it.

... Dmitry has algorithm that blows all of these away.

list p=16C64,t=ON,c=132,n=80,st=off radix dec include "P16C64.INC" buffer0 equ 0x20 bits_counted equ 0x21 a_byte equ 0x23 ORG 0 ;Reset Vector GOTO Main ORG 4 ;Interrupt Vector CLRF a_byte Main INCF a_byte,F MOVF a_byte,W CALL RR_bitcount MOVF a_byte,W CALL TC_bitcount MOVF a_byte,W CALL bitcount MOVF a_byte,W CALL look_up_bits goto Main ;***************************************************** ;RR_bitcount ; Brute force shift and count. RR_bitcount MOVWF buffer0 CLRF bits_counted RR1 CLRC RRF buffer0,F ;Get LSB and put in the carry SKPNC ;If LSB (i.e. C) is set INCF bits_counted,F ;then count it MOVF buffer0,F SKPZ GOTO RR1 RETURN ;***************************************************** ;TC_bitcount ; Test and Count ; Inputs: W - contains the byte whose bits need counting ; Outputs: bits_counted - # of bits that were set in W ;Memory Used: buffer0 ; ; 19 words, 20 cycles TC_bitcount MOVWF buffer0 CLRF bits_counted BTFSC buffer0,0 INCF bits_counted,F BTFSC buffer0,1 INCF bits_counted,F BTFSC buffer0,2 INCF bits_counted,F BTFSC buffer0,3 INCF bits_counted,F BTFSC buffer0,4 INCF bits_counted,F BTFSC buffer0,5 INCF bits_counted,F BTFSC buffer0,6 INCF bits_counted,F BTFSC buffer0,7 INCF bits_counted,F RETURN ;***************************************************** ;bitcount ; ; This algorithm loops one time for each bit that is set. ;It's based on an algorithm that deletes the right most ;bit in a byte. If the byte is 'b' then the algorithm is: ; b = b & (b-1) ; for example if ; b = xxxx1000 ; b-1 = xxxx0111 ; b & (b-1) = xxxx0000 ;The right most bit of b is deleted ; ;This algorithm comes from a book titled "Efficient C", by ;Thomas Plum and Jim Brodie. They credit Kernighan and Ritchie ;for the original insight. ; ; Inputs: W - contains the byte whose bits need counting ; Outputs: bits_counted - # of bits that were set in W ;Memory Used: buffer0 ; ; 9 words, 6 cycles min, 71 max bitcount MOVWF buffer0 ;Save a copy CLRF bits_counted ; BC1 MOVF buffer0,W ;Get the byte. (affects Z too) SKPNZ ;If no more bits are set RETURN ; then we're done INCF bits_counted,F ;Found a bit DECF buffer0,F ;"b-1" ANDWF buffer0,F ;b = b & (b-1) Delete right most bit GOTO BC1 ;***************************************************** ;look_up_bits ; ; 25 words, 20 cycles look_up_bits MOVWF buffer0 CALL look_up MOVWF bits_counted SWAPF buffer0,W CALL look_up ADDWF bits_counted,F RETURN look_up ANDLW 0x0f ADDWF PCL,F RETLW 0 ;0 RETLW 1 ;1 RETLW 1 ;2 RETLW 2 ;3 RETLW 1 ;4 RETLW 2 ;5 RETLW 2 ;6 RETLW 3 ;7 RETLW 1 ;8 RETLW 2 ;9 RETLW 2 ;a RETLW 3 ;b RETLW 2 ;c RETLW 3 ;d RETLW 3 ;e RETLW 4 ;f END

Here's more software.

This page is maintained by Scott Dattalo. You can reach me at: scott@dattalo.com. Last modified on 13DEC99.