Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #13510

Re: Counting bits using masks (riddle)

Show all headers | View raw

In article <db44c136-f82d-435e-85ec-0ecdd25c6ab9@h10g2000yqn.googlegroups.com>,
Pablo Hugo Reda  <pabloreda@gmail.com> wrote:
>0FF MOD ???  very expensive

Very expensive, on a Z80.
In this day and age you really need to specify the processor, language
and implementation and benchmark.

>
>this can help
>
>http://www.koders.com/c/fid48BA31C1DD231039FB20F72E6FCB17339E5C565A.aspx?s=time#L2
>
>you need this one?
>
>// count number of one bits
>inline uint32 ONES(uint32 x)
>{
>       uint32 t;
>       x = x - ((x >> 1) & 0x55555555);

The subtraction in the first line saves an AND,
but it is an other one than I had in mind.
Clever!

>       t = ((x >> 2) & 0x33333333);
>       x = (x & 0x33333333) + t;
>       x = (x + (x >> 4)) & 0x0F0F0F0F;

This is the trick I had in mind for saving and AND
Note that the 3333 mask is used twice.

>       x = x + (x << 8);
>       x = x + (x << 16);
>       return x >> 24;
>}
>
>:ONES | x -- u
> dup 2/ $5555555 and  -
> dup 2 >> $33333333 and  | x t
> swap $33333333 and +
> dup 4 >> + $f0f0f0f and
> dup 8 << +
> dup 16 << +
> 24 >> ;

31 woc. Mine is 29 woc, with possibility of 25 and works
for 64 bits.



>
>I don't know if work but i traslate quick
>
>good luck


--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Counting bits using masks (riddle) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-07-03 21:27 +0000
  Re: Counting bits using masks (riddle) "A. K." <akk@nospam.org> - 2012-07-03 23:51 +0200
  Re: Counting bits using masks (riddle) Pablo Hugo Reda <pabloreda@gmail.com> - 2012-07-03 15:38 -0700
    Re: Counting bits using masks (riddle) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-07-04 11:14 +0000
      Re: Counting bits using masks (riddle) Alex McDonald <blog@rivadpm.com> - 2012-07-04 04:26 -0700
        Re: Counting bits using masks (riddle) mhx@iae.nl (Marcel Hendrix) - 2012-07-04 19:30 +0200
          Re: Counting bits using masks (riddle) Alex McDonald <blog@rivadpm.com> - 2012-07-04 12:44 -0700
  Re: Counting bits using masks (riddle) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-07-04 11:40 +0000
  Re: Counting bits using masks (riddle) Mark Wills <markrobertwills@yahoo.co.uk> - 2012-07-04 14:03 -0700

csiph-web