Snippet: bitcount()
Michael Hudson
mwh21 at cam.ac.uk
Sat Jul 17 05:58:07 EDT 1999
"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.
Cheers,
Michael
--
Oh, very funny. Very sar-cah-stic. http://www.ntk.net
http://www.ntk.net/doh/options.html - ho ho
More information about the Python-list
mailing list