Bit length of int or long?

[Guido van Rossum]

> [Guido van Rossum]
> > This is not a very commonly requested operation, so there's no
> > built-in for it.
[Tim]
> Not "very", but I think it has become "common" among people use Python
> longs.  The problem is one of order:  this *should* be a constant-time
> operation, but the best hacks to do it today require both time and space
> linear in the number of bits; and in the two times you've answered this
> gripe over the years you've somehow managed twice to suggest distinct
> algorithms that take time quadratic in the number of bits <wink>.  O(N**2)
> is an absolute non-starter here, while O(N) vs O(1) for this basic operation
> propagates to screw up the timing behavior for many more complicated
> long-int algorithms too.
> 
> I don't want to see a new builtin for this (it's too specialized to justify
> polluting the builtins), and sure don't want to overload "len" either, but
> do want to add some methods to ints and longs.

In my defense: Francois didn't mention long ints in his first post. You're
right of course that a method of ints and longs is the right solution. Another
method should count '1' bits (useful when using long ints as sets of ints).

--Guido