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.