Snippet: bitcount()

[Christian Tismer]

Michael Hudson wrote:
> 
> "Tim Peters" <tim_one at email.msn.com> writes:
> > A curious thing in Python is that you can't march over the bits of a long in
> > linear time without resorting to hex() or marshal.dumps.  This really
> > complicates lookup methods, which *can* work in O(B) time straightforwardly
> > in C.
> 
> I remember being quite aggravated by this some time back, when I was
> trying to implement a reasonably fast sqrt routine for Python longs
> that worked even when they were too big to be converted into a float.
> 
> I was using the time honoured method
> 
> x -> (x+a/x)/2
> 
> which works pretty well, but to find an initial guess I thought I'd
> bitshift the number by half it's (bit) length. Finding the length
> seemed to be impossible, without doing something like
> (len(hex(a))-1)/4, which strikes me as silly, not to mention very
> memory wasteful.
> 
> Mini-proposal: len(a) for a long returns the length of the number in
> radix-256.

bitcount2 is not very slow, see here:

def bitlen1(x):
    """number of bytes necessary to store a number"""
    sign = x<0
    x = abs(long(x))
    h = hex(x)
    l = (len(h)-3)*4
    if sign and h[2] >= "8":
        l = l+1
    return (l+7)/8

import marshal

def bitlen2(x):
    """number of bytes necessary to store a number"""
    sign = x<0
    x = long(x)
    b=marshal.dumps(x)
    l = (len(b)-5)*15 / 2
    hi = ord(b[-1])*256 + ord(b[-2])
    l = l + sign -15
    while hi:
        l = l + 1
        hi = hi >> 1
    return max(1, (l+7)/8)

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101   :    *Starship* http://starship.python.net
10553 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     we're tired of banana software - shipped green, ripens at home