使用位操作高效计算Python整数二进制的前导1数量

def count_leading_ones(n: int) -> int:
    """
    计算整数二进制表示中连续前导1的数量。

    参数:
        n (int): 待计算的整数。

    返回:
        int: 连续前导1的数量。
    """
    if n == 0:
        return 0

    # 1. 获取整数n的位长度
    # 例如，n=7 (0b111), bit_length() = 3
    # n=6 (0b110), bit_length() = 3
    num_bits = n.bit_length()

    # 2. 创建一个与n位长度相同的全1掩码
    # 例如，如果num_bits=3, all_ones_mask = (1 << 3) - 1 = 8 - 1 = 7 (0b111)
    all_ones_mask = (1 << num_bits) - 1

    # 3. 对n进行位反转
    # 使用异或(XOR)操作实现位反转。
    # 例如，n=7 (0b111), all_ones_mask=0b111
    # inverted = 0b111 ^ 0b111 = 0b000
    #
    # 例如，n=6 (0b110), all_ones_mask=0b111
    # inverted = 0b110 ^ 0b111 = 0b001
    inverted = (n ^ all_ones_mask)

    # 4. 计算反转后数字的位长度，并与原始位长度相减
    # 这个差值即为原始数字的连续前导1的数量。
    #
    # 解释：
    # 原始数字 n 的 bit_length() 包含了所有从最高位1到最低位的位数。
    # 当 n 的连续前导1被反转为0后，这些0将不再计入 inverted.bit_length()。
    #
    # 示例1: n=7 (0b111)
    # num_bits = 3
    # inverted = 0b000
    # inverted.bit_length() = 0 (因为0不需要任何位表示)
    # 结果: 3 - 0 = 3
    #
    # 示例2: n=6 (0b110)
    # num_bits = 3
    # inverted = 0b001
    # inverted.bit_length() = 1 (表示0b1需要1位)
    # 结果: 3 - 1 = 2
    return num_bits - inverted.bit_length()

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

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))
print("stringify", timeit.timeit(stringify, number=1000000))

bitwise 0.29356527600612026
stringify 0.3758607900090283