ech@spuxll.UUCP (Ned Horvath) (06/21/85)
<The line eater got Steve Jobs' old job> > The following 5 instruction routine is written in 68000 code. > What does it do? > > ; D0 and D1 are 32 bit registers. > > move.l d0,d1 ; d1 := d0 > bra.s L2 ; goto L2 > L1: sub.l d1,d0 ; L1: d0 := d0 - d1 > L2: lsr.l #1,d1 ; L2: d1 := d1 div 2 > bne.s L1 ; if d1 <> 0 then goto L1 It counts the number of bits set in d0, leaving the result in d0 (and leaves d1 with a value of zero). To see this, suppose the 2^i bit is set, i>=0. On successive passes through the loop the values 2^(i-1), 2^(i-2),...2^0 will be subtracted from d0. Thus the net contribution of that bit to the final result is 2^i minus the sum of the sequence, which is 2^i-1. Hence each set bit contributes 1 to the final sum. =Ned=