on writing a number as 2^s * q, where q is odd

[Oscar Benjamin]

On Sun, 3 Dec 2023 at 10:25, Julieta Shem via Python-list
<python-list at python.org> wrote:
>
> Alan Bawden <alan at csail.mit.edu> writes:
> >
> > def powers_of_2_in(n):
> >     bc = (n ^ (n - 1)).bit_count() - 1
> >     return bc, n >> bc
>
> That's pretty fancy and likely the fastest.

It might be the fastest but it depends how big you expect n to be and
how many trailing zeros you expect. If n is a very large integer then
this does three large integer operations in (n^(n-1)).bit_count().
They are relatively fast operations but all linear in bit size. By
contrast a check like n & 1 is O(1) and half the time proves that no
further steps are necessary.

The mpmath library needs this exact operation and is generally
intended for the large n case so I checked how it is implemented
there:

https://github.com/mpmath/mpmath/blob/f13ea4dc925d522062ac734bd19a0a3cc23f9c04/mpmath/libmp/libmpf.py#L160-L177

That code is:

    # Strip trailing bits
    if not man & 1:
        t = trailtable[man & 255]
        if not t:
            while not man & 255:
                man >>= 8
                exp += 8
                bc -= 8
            t = trailtable[man & 255]
        man >>= t
        exp += t
        bc -= t

The trailtable variable is a pre-initialised list of shifts needed to
remove zeros from an 8-bit integer. The bc variable here is just
bc=man.bit_length() which is redundant but this code predates the
addition of the int.bit_length() method.

In principle this could use a large number of man>>=8 shifts which
would potentially be quadratic in the bit size of man. In practice the
probability of hitting the worst case is very low so the code is
instead optimised for the expected common case of large man with few
trailing zeros.

--
Oscar