Xref: utzoo comp.lang.c:15541 comp.std.c:687
Newsgroups: comp.lang.c,comp.std.c
Path: utzoo!utgpu!jarvis.csri.toronto.edu!dgp.toronto.edu!flaps
From: flaps@dgp.toronto.edu (Alan J Rosenthal)
Subject: Re: BIT Counting: C programming problem
Message-ID: <8901160227.AA20215@champlain.dgp.toronto.edu>
Organization: Dynamic Graphics Project, University of Toronto
References: <34389@bbn.COM> <1171@goofy.megatest.UUCP> <755@infmx.UUCP>
Date: Sun, 15 Jan 89 21:27:34 EST


There seems to be debate over whether or not the algorithm posted works, and
there was even a ``proof'' that it does work, which is very interesting.

It doesn't work for MININT unless (MININT - 1) happens to evaluate to MAXINT
(as it frequently does in real life).  On a one's complement machine, I doubt
that MININT - 1 == MAXINT very often; it's probably -0 (if it's not trapped).

If MININT - 1 is an overflow, the posted algorithm certainly won't give the
right answer for MININT (the right answer being 1 on a two's complement
machine, or log2(MAXINT + 1) on a one's complement machine).

ajr