Entry

bitcount

Jul 5th, 2000 10:00
Nathan Wallace, Hans Nowak, Snippet 151, Christian Tismer

"""
Packages: maths.bit_twiddling
"""
"""
> > 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)