Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.002 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'compiler': 0.05; 'pypy': 0.07; 'python': 0.09; 'subject:Python3': 0.09; 'subject:set': 0.09; 'cc:addr:python-list': 0.10; 'def': 0.10; '2.7:': 0.16; 'bitwise': 0.16; 'guessing': 0.16; 'message-id:@earthlink.net': 0.16; 'oct': 0.16; 'received:dsl.mindspring.com': 0.16; 'subject:bit': 0.16; 'to:addr:pearwood.info': 0.16; 'to:addr:steve+comp.lang.python': 0.16; "to:name:steven d'aprano": 0.16; 'string': 0.17; 'wrote:': 0.17; '>>>': 0.18; 'bit': 0.21; 'import': 0.21; 'operations.': 0.22; 'cc:2**0': 0.23; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'header :User-Agent:1': 0.26; 'am,': 0.27; '(as': 0.27; 'chris': 0.28; 'clever': 0.29; "d'aprano": 0.29; 'fast.': 0.29; 'steven': 0.29; 'unlikely': 0.29; "i'm": 0.29; 'that.': 0.30; 'fri,': 0.30; 'point': 0.31; 'int': 0.33; 'know.': 0.33; 'version': 0.34; 'skip:b 20': 0.34; 'christian': 0.34; 'faster': 0.35; 'really': 0.36; 'but': 0.36; 'compare': 0.36; "i'll": 0.36; 'skip:4 10': 0.37; 'subject:: ': 0.38; 'some': 0.38; 'times': 0.63; 'skip:n 10': 0.63; 'number:': 0.65; 'results': 0.65; '26,': 0.65; '600': 0.71; 'guessed': 0.84; 'hand,': 0.97 Date: Thu, 25 Oct 2012 09:08:39 -0700 From: Charles Hixson User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.7) Gecko/20120922 Icedove/10.0.7 MIME-Version: 1.0 To: Steven D'Aprano Subject: Re: bit count or bit set && Python3 References: <5089511E.4090009@earthlink.net> <50896152$0$29978$c3e8da3$5496439d@news.astraweb.com> In-Reply-To: <50896152$0$29978$c3e8da3$5496439d@news.astraweb.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: "comp.lang.python" X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 48 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1351199601 news.xs4all.nl 6984 [2001:888:2000:d::a6]:49570 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:32166 On 10/25/2012 08:57 AM, Steven D'Aprano wrote: > On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote: > >> On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes >> wrote: >>> Simple, easy, faster than a Python loop but not very elegant: >>> >>> bin(number).count("1") >> Unlikely to be fast. > Oh I don't know about that. Here's some timing results using Python 2.7: > > py> from timeit import Timer > py> t = Timer('bin(number).count("1")', setup='number=2**10001-1') > py> min(t.repeat(number=10000, repeat=7)) > 0.6819710731506348 > > Compare to MRAB's suggestion: > > def count_set_bits(number): > count = 0 > while number: > count += 1 > number&= number - 1 > return count > > py> t = Timer('count_set_bits(number)', > ... setup='from __main__ import count_set_bits; number=2**10001-1') > py> min(t.repeat(number=100, repeat=7)) > 4.141788959503174 > > > That makes the "inelegant" solution using bin() and count() about 600 > times faster than the mathematically clever solution using bitwise > operations. > > On the other hand, I'm guessing that PyPy would speed up MRAB's version > significantly. > > > Really nice and good to know. I had guessed the other way. (As you point out this is compiler dependent, and I'll be using Python3, but...conversion from an int to a bit string must be a *lot* faster than I had thought.) -- Charles Hixson