Message-Id: <199908140953.MAA30273@ankara.Foo.COM>
From: "S. M. Halloran" <mitch AT duzen DOT com DOT tr>
Organization: User RFC 822- and 1123-compliant
To: djgpp AT delorie DOT com
Date: Sat, 14 Aug 1999 13:59:02 +0200
MIME-Version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Subject: Re: Bit counting?
In-reply-to: <37B53B6E.7CF29EB1@intel.com>
X-mailer: Pegasus Mail for Win32 (v3.12)
Reply-To: djgpp AT delorie DOT com
X-Mailing-List: djgpp AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk


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