Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!cs.uu.nl!news.stack.nl!.POSTED!not-for-mail
From: Willem <willem@toad.stack.nl>
Newsgroups: comp.theory,comp.programming,sci.math
Subject: Re: n bits on of m bits
Date: Tue, 20 Dec 2011 10:05:37 +0000 (UTC)
Organization: Stack Usenet News Service
Lines: 34
Message-ID: <slrnjf0nfh.r2q.willem@toad.stack.nl>
References: <4344a25e-7fd5-43c5-b43a-a004c9f5f2ad@y7g2000vbe.googlegroups.com> <9l9q13F2g7U1@mid.individual.net> <jcoeou$777$2@odin.sdf-eu.org> <8RPHq.28946$8O1.13912@newsfe07.iad>
NNTP-Posting-Host: toad.stack.nl
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Trace: mud.stack.nl 1324375537 16380 2001:610:1108:5010::135 (20 Dec 2011 10:05:37 GMT)
X-Complaints-To: abuse@stack.nl
NNTP-Posting-Date: Tue, 20 Dec 2011 10:05:37 +0000 (UTC)
User-Agent: slrn/0.9.9p1 (FreeBSD)
Xref: x330-a1.tempe.blueboxinc.net comp.theory:1490 comp.programming:1127

Daniel Pitts wrote:
) On 12/19/11 2:44 PM, kym@kymhorsell.com wrote:
)> In sci.math The Last Danish Pastry<clivet@gmail.com>  wrote:
)> ....
)>>   public static int CountBinaryOnes(long x)
)>>   {
)>>     int result = 0;
)>>
)>>     while (x>  0)
)>>     {
)>>       ++result;
)>>       x&= x-1;
)>
)> The traditional method on 2s compl machinery is
)> 	x&= -x;
)>
)
) I've seen cleverer ways that are O(logn) best/worse case.

None of which is relevant to the OP because he wants to enumerate all
n-bit numbers that have exactly m bits set, and that can be done in
O(Choose(m,n)) time, instead of the O(2^n*logn) that this would do.

Hell, even if you just enumerated over all 2^n numbers you could still
keep/update a parallel count in O(1) time per step.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT