How would you write this procedure?

--8<---------------cut here---------------start------------->8---
def powers_of_2_in(n):
s = 0
while "I still find factors of 2 in n...":
q, r = divmod(n, 2)
if r == 0:
s = s + 1
n = n // 2
else:
return s, n
--8<---------------cut here---------------end--------------->8---

def powers_of_2_in(n):
s = 0
while n % 2 == 0:
s += 1
n = n // 2
return s, n

> On 30 Nov 2023, at 02:44, Julieta Shem via Python-list <python-list@python.org> wrote:
>
> How would you write this procedure?
>
> --8<---------------cut here---------------start------------->8---
> def powers_of_2_in(n):
> s = 0
> while "I still find factors of 2 in n...":
> q, r = divmod(n, 2)
> if r == 0:
> s = s + 1
> n = n // 2
> else:
> return s, n
> --8<---------------cut here---------------end--------------->8---
> --
> https://mail.python.org/mailman/listinfo/python-list

On 2023-11-29 at 21:44:01 -0300,
Julieta Shem via Python-list <python-list@python.org> wrote:

> How would you write this procedure?
>
> --8<---------------cut here---------------start------------->8---
> def powers_of_2_in(n):
> s = 0
> while "I still find factors of 2 in n...":
> q, r = divmod(n, 2)
> if r == 0:
> s = s + 1
> n = n // 2
> else:
> return s, n
> --8<---------------cut here---------------end--------------->8---

What's wrong with what you have?

Julieta Shem <jshem@yaxenu.org> writes:

How would you write this procedure?
def powers_of_2_in(n):
...

def powers_of_2_in(n):
return (n ^ (n - 1)).bit_count() - 1

Dom Grigonis ha scritto:
> def powers_of_2_in(n):
> s = 0
> while n % 2 == 0:
> s += 1
> n = n // 2
> return s, n
>

Good solution, unfortunately if the input data is zero, the function
never ends.

>> On 30 Nov 2023, at 02:44, Julieta Shem via Python-list <python-list@python.org> wrote:
>>
>> How would you write this procedure?
>>
>> --8<---------------cut here---------------start------------->8---
>> def powers_of_2_in(n):
>> s = 0
>> while "I still find factors of 2 in n...":
>> q, r = divmod(n, 2)
>> if r == 0:
>> s = s + 1
>> n = n // 2
>> else:
>> return s, n
>> --8<---------------cut here---------------end--------------->8---
>> --
>> https://mail.python.org/mailman/listinfo/python-list
>

Alan Bawden ha scritto:
> Julieta Shem <jshem@yaxenu.org> writes:
>
> How would you write this procedure?
> def powers_of_2_in(n):
> ...
>
> def powers_of_2_in(n):
> return (n ^ (n - 1)).bit_count() - 1
>

Great solution, unfortunately the return value is not a tuple as in the
OP version. Maybe in this way?

def powers_of_2_inB(n):
bc = (n ^ (n - 1)).bit_count() - 1
return bc, int(n / (1 << bc))

jak <nospam@please.ty> writes:

Alan Bawden ha scritto:
> Julieta Shem <jshem@yaxenu.org> writes:
>
> How would you write this procedure?
> def powers_of_2_in(n):
> ...
>
> def powers_of_2_in(n):
> return (n ^ (n - 1)).bit_count() - 1
>

Great solution, unfortunately the return value is not a tuple as in the
OP version. Maybe in this way?

def powers_of_2_inB(n):
bc = (n ^ (n - 1)).bit_count() - 1
return bc, int(n / (1 << bc))

Good point. I overlooked that. I should have written:

def powers_of_2_in(n):
bc = (n ^ (n - 1)).bit_count() - 1
return bc, n >> bc

Alan Bawden <alan@csail.mit.edu> writes:

> jak <nospam@please.ty> writes:
>
> Alan Bawden ha scritto:
> > Julieta Shem <jshem@yaxenu.org> writes:
> >
> > How would you write this procedure?
> > def powers_of_2_in(n):
> > ...
> >
> > def powers_of_2_in(n):
> > return (n ^ (n - 1)).bit_count() - 1
> >
>
> Great solution, unfortunately the return value is not a tuple as in the
> OP version. Maybe in this way?
>
> def powers_of_2_inB(n):
> bc = (n ^ (n - 1)).bit_count() - 1
> return bc, int(n / (1 << bc))
>
> Good point. I overlooked that. I should have written:
>
> 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.

I was pretty happy with a recursive version. If I'm not mistaken,
nobody has offered a recursive version so far. It's my favorite
actually because it seems to be the clearest one.

--8<---------------cut here---------------start------------->8---
def powers_of_2_in(n):
if remainder(n, 2) != 0:
return 0, n
else:
s, r = powers_of_2_in(n // 2)
return 1 + s, r
--8<---------------cut here---------------end--------------->8---

Julieta Shem ha scritto:
> Alan Bawden <alan@csail.mit.edu> writes:
>
>> jak <nospam@please.ty> writes:
>>
>> Alan Bawden ha scritto:
>> > Julieta Shem <jshem@yaxenu.org> writes:
>> >
>> > How would you write this procedure?
>> > def powers_of_2_in(n):
>> > ...
>> >
>> > def powers_of_2_in(n):
>> > return (n ^ (n - 1)).bit_count() - 1
>> >
>>
>> Great solution, unfortunately the return value is not a tuple as in the
>> OP version. Maybe in this way?
>>
>> def powers_of_2_inB(n):
>> bc = (n ^ (n - 1)).bit_count() - 1
>> return bc, int(n / (1 << bc))
>>
>> Good point. I overlooked that. I should have written:
>>
>> 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.
>
> I was pretty happy with a recursive version. If I'm not mistaken,
> nobody has offered a recursive version so far. It's my favorite
> actually because it seems to be the clearest one.
>
> --8<---------------cut here---------------start------------->8---
> def powers_of_2_in(n):
> if remainder(n, 2) != 0:
> return 0, n
> else:
> s, r = powers_of_2_in(n // 2)
> return 1 + s, r
> --8<---------------cut here---------------end--------------->8---
>

for n = 0 your function get stack overflow

jak <nospam@please.ty> writes:

[...]

>> --8<---------------cut here---------------start------------->8---
>> def powers_of_2_in(n):
>> if remainder(n, 2) != 0:
>> return 0, n
>> else:
>> s, r = powers_of_2_in(n // 2)
>> return 1 + s, r
>> --8<---------------cut here---------------end--------------->8---
>
> for n = 0 your function get stack overflow

That's right. Let's say ``assert n > 0'' before we say ``if''.

Julieta Shem ha scritto:
> jak <nospam@please.ty> writes:
>
> [...]
>
>>> --8<---------------cut here---------------start------------->8---
>>> def powers_of_2_in(n):
>>> if remainder(n, 2) != 0:
>>> return 0, n
>>> else:
>>> s, r = powers_of_2_in(n // 2)
>>> return 1 + s, r
>>> --8<---------------cut here---------------end--------------->8---
>>
>> for n = 0 your function get stack overflow
>
> That's right. Let's say ``assert n > 0'' before we say ``if''.
>

....or just:

....
if n == 0 or remainder(n, 2) != 0:
....

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

Oscar Benjamin ha scritto:
> On Sun, 3 Dec 2023 at 10:25, Julieta Shem via Python-list
> <python-list@python.org> wrote:
>>
>> Alan Bawden <alan@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
>

HI,
I would turn the question to you: how big do you expect the value to
manage?
In a 'big numbers' context or when you need to convert a large amount of
values at the same time, your comment is absolutely valid, it is less
valid if the values can be represented with 64 bits.
I'll try to imagine the worst case in 64 bit:

b64Max=0xFFFFFFFFFFFFFFFF
i=1
while True:
i *= 2
if not i <= b64Max:
break
else:
n=i
n 9223372036854775808

If we now use the function being discussed:

powers_of_2_in(n)
(63, 1)

we can see that the bit_count() method had to do 63 iterations to count
the bits. It probably had to find the highest bit first but what if it
had a simple algorithm inside like this:

def h_bit(val):
tbits = 0
bits = 64 // 2
b64Max = 0xFFFFFFFFFFFFFFFFF
while bits > 0:
if (b64Max << bits) & val:
val >>= bits
tbits += bits
bits //= 2
return tbits

would only add 6 more iterations for values needing 64 bits (7
interactions for 128 bits, 3 if 8 bits)

If we use the library you suggest for a single value or a non-'big
numbers' value (e.g. 2048 bit) the initialization alone would be slower
than the function in question. The table you are talking about is
initialized in the following way:

trailtable = [trailing(n) for n in range(256)]

(it calls a function 256 times)

This is why I think that what you said is true but it depends a lot on
the context and to all this I would add that the best cases are much
greater than the worst cases.

e.g.:
powers_of_2_in(n + 1)
(0, 9223372036854775809)
powers_of_2_in(n - 1)
(0, 9223372036854775807)

(probably only 1 interaction)

jak <nospam@please.ty> writes:

Oscar Benjamin ha scritto:
...
If we now use the function being discussed:

powers_of_2_in(n)
(63, 1)

we can see that the bit_count() method had to do 63 iterations to count
the bits....

I certainly hope that the bit_count method doesn't count bits by
iterating over them one-by-one. You can count bits _much_ faster than
that.

You can count the bits in a 62-bit number as follows:

def bit_count_62(n):
n = (n - ((n >> 1) & 0o333333333333333333333)
- ((n >> 2) & 0o111111111111111111111))
n = ( (n & 0o307070707070707070707)
+ ((n & 0o070707070707070707070) >> 3))
return n % 63

Then if you want to count the bits in arbitrarily large integers, you
iterate over them in N-bit chunks, for some N <= 62. Your choice of N
will depend on how you represent your big integers. Probably N is 56 or
48 or 32.

And why 62 bits? Because the bit_count method is certainly written in
C, where every step in bit_count_62 would use 64-bit integers.

If you like this sort of stuff, check out the book "Hacker's Delight" by
Henry Warren. See <https://en.wikipedia.org/wiki/Hacker%27s_Delight>.

- Alan

Alan Bawden ha scritto:
> If you like this sort of stuff, check out the book "Hacker's Delight" by
> Henry Warren. See<https://en.wikipedia.org/wiki/Hacker%27s_Delight>.

Thank you for your suggestion. Really interesting. Just for fun I tried
to port the function to 64 bit:

def bit_count_64(n):
lt = n >> 62
n &= (~(0x3f << 62)) & ((1 << 63) - 1)
n = (n - ((n >> 1) & 0o333333333333333333333)
- ((n >> 2) & 0o111111111111111111111))
n = ( (n & 0o307070707070707070707)
+ ((n & 0o070707070707070707070) >> 3))
return (n % 63) + (0, 1, 1, 2)[lt]

n=0xffffffffffffffff
bit_count_64(n)
64

n=0x3ffffffffffffffe
bit_count_64(n)
61

bit_count_64(1 << 63)
1

....in C it would have been simpler :^)