Python int 二进制表示中连续前导 1 的计数

Question

如何应用 Python 位运算来有效计算整数二进制表示中连续前导 1 的数量。

比如说，

内格	二进制表示法	# 连续领先 1
0	0b0	0
1	0b1	1
2	0b10	1
3	0b11	2
4	0b100	1
5	0b101	1
6	0b110	2
7	0b111	3

这个问题可以通过字符串操作来解决，如

lambda x: f"{x:b}0".index("0")

，但我正在寻找一种无需字符串转换的按位操作。

Answer 1

最终自己解决了。

def count_leading_ones(n: int) -> int:
    all_ones_mask = (1 << n.bit_length()) - 1
    inverted = (n ^ all_ones_mask)
    return n.bit_length() - inverted.bit_length()

说明

关键步骤是反转 n 的位（将 0 替换为 1，反之亦然）。 当前导 1 变为 0 时，它们将不再被拾取为

bit_length

的一部分。

然后，我们可以通过从之前的

bit_length

中减去反转后的

bit_length

来计算有多少站点掉落。这给出了存在的前导 1 的数量。

示例

以下是 0 到 16 中前导 1 的计数，

>>> for i in range(8):
...     print(f"{i} {bin(i)}: {count_leading_ones(i)}")
... 
0 0b0: 0
1 0b1: 1
2 0b10: 1
3 0b11: 2
4 0b100: 1
5 0b101: 1
6 0b110: 2
7 0b111: 3

性能测试

按位方法大约快 30%。

这是时间安排，

>>> import timeit
>>> n = 123456
>>> bitwise = lambda: n.bit_length() - ((n ^ ((1 << n.bit_length()) - 1)).bit_length())
>>> stringify = lambda: f"{n:b}0".index("0")
>>> print("bitwise", timeit.timeit(bitwise, number=1000000))
bitwise 0.29356527600612026
>>> print("stringify", timeit.timeit(stringify, number=1000000))
stringify 0.3758607900090283