On Sun, 3 Dec 2023 at 10:25, Julieta Shem via Python-list <python-list@python.org> wrote: > > Alan Bawden <a...@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 -- https://mail.python.org/mailman/listinfo/python-list
