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
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
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
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---
--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''.
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
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>.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 300 |
Nodes: | 16 (3 / 13) |
Uptime: | 72:18:10 |
Calls: | 6,714 |
Calls today: | 2 |
Files: | 12,246 |
Messages: | 5,357,080 |