Snippet: bitcount()

[Michael Hudson]

Christian Tismer <tismer at appliedbiometrics.com> writes:

> > 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)

Still chews gobs of memory though... is there any way of converting
longs <-> arrays? That'd do the trick, though you'd still end up
copying, no doubt. Still, I don't think I'm being realistic to talk of
dealing with numbers so large copying them is an issue in Python. It's
all just for play, anyway.

Cheers,
Michael

-- 
Oh, very funny. Very sar-cah-stic.         http://www.ntk.net
http://www.ntk.net/doh/options.html - ho ho