如何用Python位运算高效统计整数二进制的连续前导1个数

需求明确：给定整数，无需字符串转换，纯靠位运算统计其二进制表示中连续前导1的数量，比如0返回0，3（0b11）返回2，7（0b111）返回3等。

方法1：二分法位运算（高效，适配固定位数整数） #

通过二分思想结合位掩码快速定位前导1的长度，时间复杂度为O(log n)（n为整数的二进制位数），适合处理固定位数的整数（如32位、64位）。

以32位整数为例，代码实现：

def count_leading_ones(x):
    if x == 0:
        return 0
    count = 0
    # 检查高16位是否全为1
    if (x & 0xFFFF0000) == 0xFFFF0000:
        count += 16
        x <<= 16
    # 检查剩余部分的高8位
    if (x & 0xFF000000) == 0xFF000000:
        count += 8
        x <<= 8
    # 检查剩余部分的高4位
    if (x & 0xF0000000) == 0xF0000000:
        count += 4
        x <<= 4
    # 检查剩余部分的高2位
    if (x & 0xC0000000) == 0xC0000000:
        count += 2
        x <<= 2
    # 检查最高位
    if (x & 0x80000000) == 0x80000000:
        count += 1
    return count

原理：每次判断当前高位段是否全为1，若是则累加对应位数，并将该段左移移出，继续判断剩余高位，逐步缩小范围。

方法2：循环位移法（简单直观） #

通过不断左移整数，直到最高位变为0，统计位移次数即可得到前导1的数量。

代码实现：

def count_leading_ones(x):
    if x == 0:
        return 0
    count = 0
    # 以32位无符号整数为例，处理64位则将掩码改为0x8000000000000000
    while x & 0x80000000:
        count += 1
        x <<= 1
    return count

方法3：结合内置函数的位运算方案（简洁） #

利用Python内置的bit_length()获取整数二进制位数，再通过位运算推导前导1的数量：

def count_leading_ones(x):
    if x == 0:
        return 0
    bit_len = x.bit_length()
    # 构造掩码，将前导1之后的所有位置为1
    mask = (1 << bit_len) - 1
    # 异或后得到的数的最高位位置就是前导1的结束位置
    return bit_len - (x ^ mask).bit_length()

原理：x ^ mask会把前导1转为0，后续位转为1，其bit_length()的值是第一个0之后的位数，用总位数减去这个值就能得到前导1的数量。

测试验证 #

用示例中的整数测试：

test_cases = [0,1,2,3,4,5,6,7]
for num in test_cases:
    print(f"整数{num}的连续前导1个数：{count_leading_ones(num)}")

输出结果与示例完全匹配：

整数0的连续前导1个数：0
整数1的连续前导1个数：1
整数2的连续前导1个数：1
整数3的连续前导1个数：2
整数4的连续前导1个数：1
整数5的连续前导1个数：1
整数6的连续前导1个数：2
整数7的连续前导1个数：3

内容的提问来源于stack exchange，提问作者mmore500