Re: Variation of bit-counting

From: CBFalconer (cbfalconer_at_yahoo.com)
Date: 03/03/05 

Date: Thu, 03 Mar 2005 15:31:11 GMT

Gerry Quinn wrote:
> willem@stack.nl says...
>> Thomas wrote:
>>) Jon Harrop coughed up:
>>)> Michael Jørgensen wrote:
>
>>)>> I have an unsigned 32-bit number of the form 111..10...000,
>>)>> i.e. a number of ones and the rest zeros. I would like to
>>)>> count the number of ones.
>>)>>
>>)>> The usual bit-counting tricks can be used, but are there more
>>)>> efficient methods given this particular form of the number?
>>)>
>>)> As there are about 32 possible inputs, can you not just look
>>)> the answer up from a 32-element array?
>>)
>>) A 32 bit number yields over 4 billion possible inputs. That's
>>) a pretty hefty array.
>>
>> You failed to notice that the number is of a specific form,
>> limiting it to 33 possible inputs.
>
> You failed to notice that finding the index into a 33-element
> array (as distinct from a 2^32-element array) is equivalent to
> the original problem of counting the ones in the 32-bit integer!

You fail to notice that a search of a 6 level deep tree can be
performed in at most 6 operations, and the failure means that the
pattern is not suitable. Success yields an immediate answer. 33
possible values, plus a not-found condition, implies 6 levels. 

-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson