Snippet: bitcount()
Christian Tismer
tismer at appliedbiometrics.com
Sat Jul 17 08:19:58 EDT 1999
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
More information about the Python-list
mailing list