计算基数 2 中尾随零数的 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
的反向二进制表示

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

有没有单语句的方法来做到这一点？

我的最终目标是计算 2 的最高次方的 Pythonic 方法，它除以 n 没有余数，所以任何方法都不是通过计算尾随零来实现的字符串也很受欢迎。

Answer 1

避免使用 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 时，所有前导零和 1 位都相反，但最后 1 位和所有尾随零在这两种方式下都相同。

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