Python位运算：高效统计整数二进制表示中的连续前导1

def count_leading_ones(n: int) -> int:
    """
    使用位运算统计整数二进制表示中连续前导1的数量。
    """
    if n == 0:
        return 0

    # 1. 获取整数的实际位长度
    # 例如，对于 6 (0b110)，bit_length() 返回 3
    # 对于 7 (0b111)，bit_length() 返回 3
    original_bit_length = n.bit_length()

    # 2. 创建一个与 n 具有相同位长度的全1掩码
    # 例如，如果 original_bit_length 是 3，则 (1 << 3) - 1 得到 0b111 (7)
    all_ones_mask = (1 << original_bit_length) - 1

    # 3. 将 n 与全1掩码进行位异或操作
    # 异或操作的效果是：如果对应位相同则为0，不同则为1。
    # 结合全1掩码，这意味着 n 中的 0 变为 1，1 变为 0。
    # 例如： n = 0b110 (6)
    #        all_ones_mask = 0b111 (7)
    #        inverted = 0b110 ^ 0b111 = 0b001 (1)
    # 例如： n = 0b111 (7)
    #        all_ones_mask = 0b111 (7)
    #        inverted = 0b111 ^ 0b111 = 0b000 (0)
    inverted = (n ^ all_ones_mask)

    # 4. 计算反转后数字的位长度
    # 对于 inverted = 0b001 (1)，bit_length() 返回 1
    # 对于 inverted = 0b000 (0)，bit_length() 返回 0
    inverted_bit_length = inverted.bit_length()

    # 5. 结果是原始位长度减去反转后数字的位长度
    # 这个差值代表了原始数字中前导1的数量。
    # 例如： original_bit_length = 3, inverted_bit_length = 1  => 3 - 1 = 2 (正确 for 0b110)
    # 例如： original_bit_length = 3, inverted_bit_length = 0  => 3 - 0 = 3 (正确 for 0b111)
    return original_bit_length - inverted_bit_length

def count_leading_ones(n: int) -> int:
    """
    使用位运算统计整数二进制表示中连续前导1的数量。
    """
    if n == 0:
        return 0

    original_bit_length = n.bit_length()
    all_ones_mask = (1 << original_bit_length) - 1
    inverted = (n ^ all_ones_mask)
    inverted_bit_length = inverted.bit_length()

    return original_bit_length - inverted_bit_length

# 示例：计算0到7的连续前导1数量
print("--- 0到7的连续前导1数量 ---")
for i in range(8):
    print(f"{i} {bin(i)}: {count_leading_ones(i)}")

# 更多示例
print("\n--- 更多示例 ---")
print(f"15 (0b1111): {count_leading_ones(15)}") # 4
print(f"8 (0b1000): {count_leading_ones(8)}")   # 1
print(f"12 (0b1100): {count_leading_ones(12)}") # 2
print(f"0 (0b0): {count_leading_ones(0)}")     # 0

--- 0到7的连续前导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

--- 更多示例 ---
15 (0b1111): 4
8 (0b1000): 1
12 (0b1100): 2
0 (0b0): 0

import timeit

n_test = 123456789 # 用于测试的整数

# 位运算方法
bitwise_method = lambda: n_test.bit_length() - ((n_test ^ ((1 << n_test.bit_length()) - 1)).bit_length())

# 字符串转换方法
stringify_method = lambda: f"{n_test:b}0".index("0")

print(f"测试整数: {n_test} ({bin(n_test)})")
print(f"位运算方法耗时: {timeit.timeit(bitwise_method, number=1000000):.6f} 秒")
print(f"字符串方法耗时: {timeit.timeit(stringify_method, number=1000000):.6f} 秒")

测试整数: 123456789 (0b111010110111100110100010101)
位运算方法耗时: 0.29xxx 秒
字符串方法耗时: 0.37xxx 秒