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 Newsgroups: comp.theory,comp.programming,sci.math Subject: Re: n bits on of m bits Date: Tue, 20 Dec 2011 16:00:37 +0000 (UTC) Organization: Stack Usenet News Service Lines: 23 Message-ID: References: <4344a25e-7fd5-43c5-b43a-a004c9f5f2ad@y7g2000vbe.googlegroups.com> <9l9q13F2g7U1@mid.individual.net> <8RPHq.28946$8O1.13912@newsfe07.iad> <5M6dnXNqI40qO23TnZ2dnUVZ_q6dnZ2d@earthlink.com> <89eab275-fd81-42fb-8f66-2e8a5d089ca7@x7g2000yqb.googlegroups.com> 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 1324396837 29479 2001:610:1108:5010::135 (20 Dec 2011 16:00:37 GMT) X-Complaints-To: abuse@stack.nl NNTP-Posting-Date: Tue, 20 Dec 2011 16:00:37 +0000 (UTC) User-Agent: slrn/0.9.9p1 (FreeBSD) Xref: x330-a1.tempe.blueboxinc.net comp.theory:1493 comp.programming:1130 Dave wrote: ) On Dec 20, 9:16?am, Patricia Shanahan wrote: )> If the input is narrow enough to fit in an hardware data type that has )> fast addition, bit operations, and shifts, counting the one bits only )> takes log(w) steps, where w is the width in bits, not the value of the )> input number. ) ) The code I posted in http://groups.google.com/group/sci.math/msg/cb1e398f74688e66 ) steps from one number with n bits set directly to the next one, so the ) loop count is mCn. Making the same assumption about hardware data types as above, of course. But that goes for the complexity of just about all algorithms out there, really. 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