Message-Id: <37B58FF7.53737186@intel.com>
Date: Sat, 14 Aug 1999 17:49:11 +0200
From: Kurt Alstrup <kurt DOT alstrup AT intel DOT com>
Organization: Intel Denmark Aps
X-Mailer: Mozilla 4.51 [en] (WinNT; U)
X-Accept-Language: en
Mime-Version: 1.0
To: djgpp AT delorie DOT com
Subject: Re: Bit counting?
References: <199908140953 DOT MAA30273 AT ankara DOT Foo DOT COM>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reply-To: djgpp AT delorie DOT com

Hmm.. I was wrong about the '&' versus '%' suggested in the previous mail. I does,
as you point out, not work since that trick work on powers of 2, which 077 is not.
I appollogise for any misleading this might have caused.

Readability and understandability is indeed a virtue, but sometimes hacks like
these
have their right. For readbility I'd definitly go for a loop just counting the bits
one
by one, but it comes at a cost in CPU cycles which, in my experience, often is a
a costly resource. The origin of that routine is from X11 i think.

Kurt Alstrup

"S. M. Halloran" wrote:

> I have heard that a general philosophy is for the programmer to make his code
> readable and understandable:
>
>     a = b % 256;
>
> is much more understandable than
>
>     a = b & 255;
>
> for the intent is to take the remainder of a div by 256, something not obvious
> in the second statement.
>
> That is, optimizing of that type should be left to the compiler and not the
> programmer.  A compiler worth its salt should easily optimize that to the
> faster instruction, or fewer instructions.
>
> On 14 Aug 99, Kurt Alstrup was found to have commented thusly:
>
> > Well ... Looking at it again then a modulo 077 (= 0x3f) could be
> > accompliced by using '&' instead.
>
> Evaluate:
>
>     x % 077    where x >= 077
>
> and tell me if it is equal to
>
>     x & 077    where x >= 077
>
> This is probably why C/C++ programmers should stick with using the '%' operator
> rather than trying to do the compiler's job for it.
>
> > Thus the line
> >
> >     return (int) (((y + (y >> 3)) & 030707070707) & 077);
> >
> > should do the same without using a potential slow mod operator.
> >
> > Kurt Alstrup
>
> > Klaas wrote:
> >
> > > Kurt Alstrup wrote:
> > > >
> > > > Try this little function, I guess it may gain if written in assembly
> > > > though ..
> > > >
> > > > /*
> > > >  *      Ones
> > > >  *
> > > >  * This magic counts the number of bits in one longword
> > > >  */
> > > >
> > > > int
> > > > Ones(unsigned long mask)
> > > > {
> > > >   register unsigned long y;
> > > >
> > > >   y = (mask >> 1) & 033333333333;
> > > >   y = mask - y - ((y >>1) & 033333333333);
> > > >   return (int) (((y + (y >> 3)) & 030707070707) % 077);
> > > > }
> > > >
> > > > Regards,
> > > > Kurt Alstrup
> > >
> > > Doesn't the modulo make it rather slow?
> > >
> > > -Mike
>
> Mitch Halloran
> Research (Bio)chemist
> Duzen Laboratories Group
> Ankara       TURKEY