Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed5.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.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'python3': 0.05; 'test,': 0.05; 'bits': 0.07; '32-bit': 0.09; 'cc:addr:googlegroups.com': 0.09; 'integers': 0.09; 'subject:Python3': 0.09; 'subject:set': 0.09; 'weak': 0.09; 'cc:addr:python-list': 0.10; 'useful,': 0.13; 'decent': 0.16; 'equivalents': 0.16; 'integers,': 0.16; 'message- id:@earthlink.net': 0.16; 'operation.': 0.16; 'otoh,': 0.16; 'pointers,': 0.16; 'received:dsl.mindspring.com': 0.16; 'set,': 0.16; 'still,': 0.16; 'subject:bit': 0.16; 'string': 0.17; 'wrote:': 0.17; 'integer': 0.17; 'solution.': 0.18; 'tests': 0.18; 'sort': 0.21; 'bit': 0.21; 'logical': 0.22; "i'd": 0.22; 'cc:2**1': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply- To:1': 0.25; 'header:User-Agent:1': 0.26; '[1]': 0.27; 'converting': 0.27; 'operations,': 0.27; 'options': 0.27; "doesn't": 0.28; 'correct': 0.28; 'this?': 0.28; 'decide': 0.28; '(possibly': 0.29; 'overhead': 0.29; 'surprised': 0.29; 'url:code': 0.29; 'probably': 0.29; "i'm": 0.29; 'that.': 0.30; 'thursday,': 0.30; 'implement': 0.32; 'file': 0.32; 'function.': 0.33; "won't": 0.35; 'there': 0.35; 'next': 0.35; 'add': 0.36; 'but': 0.36; 'cc:no real name:2**1': 0.36; 'anything': 0.36; "i'll": 0.36; 'should': 0.36; 'october': 0.37; 'drop': 0.37; 'subject:: ': 0.38; 'store': 0.38; 'think': 0.40; 'url:p': 0.63; 'times': 0.63; 'email addr:gmail.com': 0.63; 'more': 0.63; 'union': 0.66; 'intending': 0.84; 'light-weight': 0.84; 'net,': 0.84; 'risks.': 0.84; 'approach.': 0.91 Date: Fri, 26 Oct 2012 09:30:21 -0700 From: Charles Hixson User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.7) Gecko/20120831 Firefox/10.0.7 Iceape/2.7.7 MIME-Version: 1.0 To: casevh@gmail.com Subject: Re: bit count or bit set && Python3 References: <0a70ae3c-5058-4b12-89c7-30a27aa8baa8@googlegroups.com> In-Reply-To: <0a70ae3c-5058-4b12-89c7-30a27aa8baa8@googlegroups.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: python-list@python.org, comp.lang.python@googlegroups.com 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: 43 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1351269379 news.xs4all.nl 6942 [2001:888:2000:d::a6]:55373 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:32225 casevh@gmail.com wrote: > On Thursday, October 25, 2012 7:56:25 AM UTC-7, Charles Hixson wrote: >> In Python3 is there any good way to count the number of on bits in an >> integer (after an& operation)? > You may want to look at gmpy2[1] and the popcount() function. > >> Alternatively, is there any VERY light-weight implementation of a bit >> set? I'd prefer to use integers, as I'm probably going to need >> thousands of these, if the tests work out. But before I can test, I >> need a decent bit counter. (shift, xor,&, and | are already present >> for integer values, but I also need to count the number of "true" items >> after the logical operation. So if a bitset is the correct approach, >> > Whether or not gmpy2 is considered light-weight is debateable. :) > >> I'll need it to implement those operations, or their equivalents in >> terms of union and intersection.) >> >> >> >> Or do I need to drop into C for this? >> > [1] http://code.google.com/p/gmpy/ > >> >> -- >> >> Charles Hixson I can see many times when that would be useful, but for this particular case I think that bin(val).count("1") is probably the better solution. The other options that I need are already available directly in integer numbers, and I will be surprised if I need more than a 32-bit set, so integers should be a reasonable approach. It doesn't seem to have the overhead that I feared a string conversion would have (possibly because converting an integer to a bit string is trivial), so I don't think that gmpy would add value to this program. Next I need to decide about weak pointers, and then shelve vs. tokyocabinet. (I sort of don't like shelve, because of its use of pickle, with the attendent security risks. OTOH, the file will be local to the computer, not going over the net, which minimizes that. Still, I may decide to reimplement it using ast.literal_eval, as I'm not intending to store anything that it won't handle.