Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site spuxll.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!spuxll!ech
From: ech@spuxll.UUCP (Ned Horvath)
Newsgroups: net.puzzle
Subject: *SPOILER* Short sequences of assembly language instructions
Message-ID: <672@spuxll.UUCP>
Date: Fri, 21-Jun-85 02:32:36 EDT
Article-I.D.: spuxll.672
Posted: Fri Jun 21 02:32:36 1985
Date-Received: Sun, 23-Jun-85 00:20:43 EDT
Organization: AT&T Information Systems, South Plainfield NJ
Lines: 23

<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=