python - 如何跳过内置 int 中的尾随零位？

Question

有没有一些快速的方法来获取 Python3 内置整数中尾随零的数量？

例如，如果我想检查是否有 4 个尾随零，我可以执行以下操作:

>>> some_integer & 15

或者对于 8 个尾随零:

>>> some_integer & 255

如果结果不为0，则前4位或8位有1。

有没有办法以一般方式执行此操作？我的目标是通过 >>> 运算符跳过任意数量的尾随零。

Answer 1

您可以使用按位算术(对于正值和负值，但不包括 0，因为没有 1 可跟踪，因此未定义其行为):

(x & -x).bit_length() - 1

或:

(x ^ -x).bit_lenght() - 2

或者，可能有更有趣的 0 行为(感谢@TomKarzes 评论):

(x ^ (x - 1)).bit_length() - 1

要了解它们的工作原理，让我们考虑最后一个表达式。当我们执行 x - 1 时，如果 x 是奇数，则只有那个位被翻转，然后当我们执行 xor ^ 时，这是唯一的在操作中幸存下来的位。类似地，当 x 不是奇数时，每个尾随零都将翻转为 1，尾随 1 将翻转为 0，所有其他位都保持不变，然后我们执行 xor 所有位直到尾随 1 被设置。然后，int.bit_length()计算找到了多少个有效位，-1 只是一个常量偏移量，我们需要获得“尾随零的数量”。

为什么第一种方法也有效是由于负数的二补码表示。确切的细节留给读者作为练习。

为了证明它们有效:

for i in range(-15, 16): 
     print(
         f'{i:5b}',
         f'{i ^ -i:3d}',
         f'{(i & -i).bit_length() - 1:2d}',
         f'{(i ^ -i).bit_length() - 2:2d}',
         f'{(i ^ (i - 1)).bit_length() - 1:2d}') 

-1111  -2  0  0  0
-1110  -4  1  1  1
-1101  -2  0  0  0
-1100  -8  2  2  2
-1011  -2  0  0  0
-1010  -4  1  1  1
-1001  -2  0  0  0
-1000 -16  3  3  3
 -111  -2  0  0  0
 -110  -4  1  1  1
 -101  -2  0  0  0
 -100  -8  2  2  2
  -11  -2  0  0  0
  -10  -4  1  1  1
   -1  -2  0  0  0
    0   0 -1 -2  0
    1  -2  0  0  0
   10  -4  1  1  1
   11  -2  0  0  0
  100  -8  2  2  2
  101  -2  0  0  0
  110  -4  1  1  1
  111  -2  0  0  0
 1000 -16  3  3  3
 1001  -2  0  0  0
 1010  -4  1  1  1
 1011  -2  0  0  0
 1100  -8  2  2  2
 1101  -2  0  0  0
 1110  -4  1  1  1
 1111  -2  0  0  0

注意 0 输入的两个表达式的不同行为。特别是，如果您希望 0 输入生成 0，(x ^ (x - 1)).bit_length() - 1 可能会导致更简单的表达式> 输出。

---

在速度方面，这应该比任何基于循环的解决方案都快得多，并且与基于查找的解决方案相当(但没有大小限制并且不使用额外的内存):

def trail_zero_loop(x):
    if x != 0:
        k = -1
        r = 0
        while not r:
            # x, r = divmod(x, 2)  # ~15% slower
            r = x % 2
            x = x // 2
            k += 1
        return k
    else:
        return -1

def trail_zero_and(x):
    return (x & -x).bit_length() - 1

def trail_zero_xor(x):
    if x != 0:
        # return (x ^ -x).bit_length() - 2  # ~1% slower
        return (x ^ (x - 1)).bit_length() - 1
    else:
        return -1

_LOOKUP =[ 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 ]


def trail_zero_lookup(x):
    if x != 0:
        return _LOOKUP[(x & -x) % 37]
    else:
        return -1

n = 2 ** 30
%timeit trail_zero_loop(n)
# 3.15 µs ± 25.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 
%timeit trail_zero_and(n)
# 228 ns ± 9.87 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit trail_zero_xor(n)
# 253 ns ± 7.25 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit trail_zero_lookup(n)
# 294 ns ± 1.81 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

最终的额外位移操作只需要几纳秒，因此在这里应该无关紧要。