本文详细介绍了如何在Python中利用位运算高效地统计一个整数二进制表示中连续前导1的数量。该方法通过巧妙地构造全1掩码并进行位异或操作，避免了字符串转换的开销，显著提升了性能。文章将深入解析核心算法，提供代码示例及性能对比，展示位操作在处理二进制数据时的强大优势。
1. 理解问题：统计连续前导1
在处理整数的二进制表示时，有时我们需要统计其从最高位开始连续的“1”的数量。例如，整数 6 的二进制表示是 0b110，其连续前导1的数量是 2。整数 7 的二进制表示是 0b111，其连续前导1的数量是 3。
下表展示了一些整数及其二进制表示和连续前导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 |
虽然可以通过将整数转换为字符串（如 f"{x:b}0".index("0")）来解决此问题，但这种方法涉及字符串操作，可能带来额外的性能开销。本教程的目标是探索一种纯粹基于位运算的高效解决方案。
立即学习“Python免费学习笔记（深入）”；
2. 位运算解决方案
核心思想是利用位异或操作来“反转”目标整数的位，并结合 bit_length() 方法来计算前导1的数量。
2.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_length2.2 算法解释
- n.bit_length(): Python的 int.bit_length() 方法返回表示该整数所需的最小位数，不包括符号位和任何前导零。例如，6 (0b110) 的 bit_length() 是 3，7 (0b111) 的 bit_length() 也是 3。这个值代表了我们关注的二进制表示的“总长度”。
- all_ones_mask = (1 : 这一步是创建一个与 n 具有相同有效位长度的全1掩码。
- 1
- 减去 1 后，0b1000 - 1 得到 0b111 (7)，即一个由 original_bit_length 个 1 组成的数。这个掩码确保了我们只在 n 的有效位范围内进行操作。
-
inverted = (n ^ all_ones_mask): 这是关键一步。位异或操作（^）会比较两个数的对应位：如果相同则结果位为0，如果不同则结果位为1。当 n 与一个全1掩码进行异或时，实际上是反转了 n 中对应位的值。
- 例如，如果 n 的某位是 1，与掩码中的 1 异或后变为 0。
- 如果 n 的某位是 0，与掩码中的 1 异或后变为 1。
- 这样，原始数字中的前导 1 序列会变成前导 0 序列，而第一个 0 则会变成 1。
-
original_bit_length - inverted.bit_length():
- 当 n 的前导 1 被反转为 0 后，这些 0 不再计入 inverted.bit_length()。
- 例如，对于 n = 0b110，original_bit_length = 3。反转后 inverted = 0b001，其 bit_length() 是 1。
- 3 - 1 = 2，这正是 0b110 的连续前导1的数量。
- 对于 n = 0b111，original_bit_length = 3。反转后 inverted = 0b000，其 bit_length() 是 0（因为0不需要任何位来表示）。
- 3 - 0 = 3，这正是 0b111 的连续前导1的数量。
3. 代码实现与示例
下面是完整的Python函数实现，并展示了其使用方式：
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
4. 性能考量
与基于字符串转换的方法相比，位运算方法通常具有更高的效率，因为它直接操作数字的二进制表示，避免了字符串的创建、解析和索引等开销。
我们可以使用 timeit 模块进行简单的性能测试：
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 秒
从上述结果可以看出，位运算方法比字符串转换方法快约30%，这在需要频繁执行此类操作的场景中尤为重要。
5. 总结与注意事项
- 优点: 位运算方法高效、简洁，避免了字符串操作的性能开销，尤其适用于对性能要求较高的场景。
- 适用性: 该方法适用于任何非负整数。对于负整数，Python的 bit_length() 行为不同（它会计算表示该负数所需的最小位数，包括符号位，例如 -1 的 bit_length() 是 0，-2 是 1），因此如果需要处理负数，则需要额外的逻辑来处理其二进制补码表示。本教程主要关注非负整数。
- 可读性: 虽然位运算可能不如字符串操作直观，但一旦理解了其原理，它提供了一种优雅且高效的解决方案。
通过掌握这种位运算技巧，开发者可以在Python中更高效地处理二进制数据，优化代码性能。
