Home Original page

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