Bit counting

>Why bother when you can simply do an eight line function?

>int bitcount(char b)
>{
>register int retval=0;

> if (a & 1) retval++;
> if (a & 2) retval++;
> if (a & 4) retval++;
> if (a & 8) retval++;
> if (a & 16) retval++;
> if (a & 32) retval++;
> if (a & 64) retval++;
> if (a & 128) retval++; 

>return retval;
>}

[...]

Because on a lot of architectures this implementation may be hideously
inefficient.  All the world is not an Intel chip, thank god.

							Ian.

> 
> >Why bother when you can simply do an eight line function?
> 
> >int bitcount(char b)
> >{
> >register int retval=0;
> 
> > if (a & 1) retval++;
> > if (a & 2) retval++;
> [...]
> 
> Because on a lot of architectures this implementation may be hideously
> inefficient.  All the world is not an Intel chip, thank god.

Okay, I'll bite this one again.

6502:
LDX #$00
LDA b
BIT #$01
BEQ +2
INX
BIT #$02
BEQ +2
INX
/\/\/\/\//\
TXA
STA returnvalue
RTS

There.  On a 6502, this too would take about 5 bytes per test * 8 tests, that's
40 bytes.  So that's about 60 bytes or so maximum for this function.  Now for
68000:

MOVE.B 0,D1
LEA A0,[address_of_parameter_b_from_stack]
MOVE.B [A0],D0
MOVE.B D0,D2
ANDI #01,D0
BEQ [skip three instructions]
ADDI #1,D1
MOVE.B D2,D0
ANDI #02,D0 
BEQ [skip three instructions]
/\/\/\/\/\/
MOV D1,[return_value_on_stack]
RET

Same commands, but on the 68K, it'll take up a bit more space, though the 68K
will run faster.

Now granted on certain machines the XOR method is faster, but is it more
obvious?  I've seen lots of "cool" code in my time.  The verdict on it is
that while it's neato whiz bang cool, it's hard to debug or update if it
needs fixing, and tends to be very non obvious.  If you use a good compiler
which has register optimization, the function done the long way will be
as fast as the XOR method, and cleaner, and in some cases actually faster.

>From: Ian Farquhar <ifarqhar@laurel.ocs.mq.edu.au>
>Date: Thu, 7 Jul 1994 12:57:54 +1000 (EST)
>
>>Why bother when you can simply do an eight line function?
                                       ~~~~~
>>int bitcount(char b)
>>{
>>register int retval=0;
>
>> if (a & 1) retval++;
>> if (a & 2) retval++;
        etc.
>>return retval;
>>}
>
>Because on a lot of architectures this implementation may be hideously
>inefficient.  All the world is not an Intel chip, thank god.

Not to mention it's only good for 8-bit words.  In my case I am working
with 16-bit data.

tw