AVR-Chat

Hi, 

> > Indeed!
> > 
> > I don't see a lot of this sort of thing anymore, here, or 
> on the piclist.
> > Used to be, several years ago..
> > 
> 
> OK - how about another classic problem. Again, fine when you 
> know but worth looking for a solution. Efficient code for 
> counting the ones in an
> 8 or 16 bit value - say for a majority vote or some such.
> 
> Pete Harrison

unsigned count_ones(unsigned x)
{
  unsigned ones;
  for (ones = 0; x; x &= x-1)
    ++ones;
  return ones;
}

By extension you can say "does some value x have at least 2 one bits?"
easily:

// non-zero if at least two bits are set in x.
unsigned
at_least_two_1_bits_set_p(unsigned x)
{
  return x == 0 ? 0 : x & (x-1);
}

--
Paul Curtis, Rowley Associates Ltd  http://www.rowley.co.uk
CrossWorks for MSP430, ARM, AVR and (soon) MAXQ processors

Paul Curtis wrote:
> Hi, 
> 
> 
>>>Indeed!
>>>
>>>I don't see a lot of this sort of thing anymore, here, or 
>>
>>on the piclist.
>>
>>>Used to be, several years ago..
>>>
>>
>>OK - how about another classic problem. Again, fine when you 
>>know but worth looking for a solution. Efficient code for 
>>counting the ones in an
>>8 or 16 bit value - say for a majority vote or some such.
>>
>>Pete Harrison
> 
> 
 From my days using 6502 for speed, use a look up table again - but is 
that code!

Or a simple loop. Relying on the bit shifted from the accumulator goes 
into the carry, then use ADC #0. This saves testing bits and any braches 
in code.

Something similar must be possible with AVR but I don't want to stick my 
neck out too far yet, only a starter after a long break!

Richard

Mid point is to use smaller table & index it with the upper & lower 
nibble. Accessing the appropriate nibble still carries its own overhead 
so generally all of these get down to the usual speed/flash usage issues 
which makes it handy to go to CPU overkill for anything other than 
consumer products which are to be manufactured by the gazillion.

A suggestion - I agree wholeheartedly with the proposal to try to draw 
out all of the battle won integer algorithms hiding in peoples heads. It 
would be useful to toss a brief desc in the subject to make it easy to 
follow the discussion much later on when going back to explore the 
proposal. The discussion & alternate solutions can be as important as 
the eventual winner.

There was a really neat book on integer arithmetic written in the late 
60's which used to be referred to on the Forth group. Sometimes it turns 
up second hand on Amazon & is well worth finding. I will trawl the old 
forth directories & try to dig out a title.



Cheers

Don



Richard Austin wrote:
> Paul Curtis wrote:
> 
>>Hi, 
>>
>>
>>
>>>>Indeed!
>>>>
>>>>I don't see a lot of this sort of thing anymore, here, or 
>>>
>>>on the piclist.
>>>
>>>
>>>>Used to be, several years ago..
>>>>
>>>
>>>OK - how about another classic problem. Again, fine when you 
>>>know but worth looking for a solution. Efficient code for 
>>>counting the ones in an
>>>8 or 16 bit value - say for a majority vote or some such.
>>>
>>>Pete Harrison
>>
>>
>  From my days using 6502 for speed, use a look up table again - but is 
> that code!
> 
> Or a simple loop. Relying on the bit shifted from the accumulator goes 
> into the carry, then use ADC #0. This saves testing bits and any braches 
> in code.
> 
> Something similar must be possible with AVR but I don't want to stick my 
> neck out too far yet, only a starter after a long break!
> 
> Richard
> 
> 
> 
> 
>  
> Yahoo! Groups Links
> 
> 
> 
>  
> 
> 
> 


-- 
Cheers

Don Ingram


Leading Edge Design

Mob: 0418 775 670
Ph : +61 7 4942 5670
Fax: +61 7 4942 5680

P.O. Box 10326
Mt Pleasant
QLD 4740
Australia