PIC Parity - Bit Counting

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.

BACK HOME


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