Pythonic方式计算尾随零的数量

Question

我正在寻找一种Pythonic方法来计算正整数的二进制表示中的尾随零的数量n(这将表示其中最高功率2除以n没有余数).

简单的解决方案:

def CountZeros(n):
    c = 0
    while (n % 2) == 0:
        n /= 2
        c += 1
    return c

但为了以更加Pythonic的方式做到这一点,我认为我可以利用:

• bin(n)[2:],给出二进制表示 n
• bin(n)[:1:-1],它给出了反向二进制表示 n

所以我的问题可以简化为计算字符串中尾随零的数量.

有没有单一陈述方式来做到这一点？

我的最终目标是用于计算最高功率的Pythonic方法,2其中n没有余数,所以任何方法不是通过计算字符串中的尾随零来实现这一点也是值得赞赏的.

Answer 1

你可以使用str.rstrip:

def trailing(s):
    return len(s) - len(s.rstrip('0'))

Answer 2

避免使用 转换为字符串的速度是bin使用修改后的bithack 的两倍，因为我们已经有了一个有效的log2实现。

def ctz(v):
    return (v & -v).bit_length() - 1

如果输入为 0，则上述返回 -1。

使用 C 使其速度再次提高一倍：

from gmpy2 import bit_scan1 as ctz

如果输入为零，则此版本返回 None。

例如，如果输入为 20，请考虑无限二进制展开：

v    000...00010100
~v   111...11101011 (not used directly, all bits opposite)
-v   111...11101100 (-v == ~v + 1; this causes all low 1 bits to overflow and carry)
v&-v 000...00000100 (has a single 1 bit, from the carry)

当anded 时，所有前导零和一位都是相反的，但最后一位和所有尾随零在两种情况下都相同。

然后.bit_length()告诉我们整数总共使用了 3 位，因此只需减去 1 即可仅考虑零。

Answer 3

这可能会.

def trailing_zeros(n):
    s = str(n)
    return len(s)-len(s.rstrip('0'))