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

本文详细阐述了如何利用python的位操作高效计算整数二进制表示中连续前导1的数量。通过构造一个与原整数位长相同的全1掩码，对整数进行位反转，并巧妙地利用`bit_length()`属性的差值，可以避免传统的字符串转换方法，从而实现更优的性能。教程将深入解析该位操作方法的原理、提供完整的示例代码及性能对比分析。

概述

在处理整数的二进制表示时，有时需要统计其连续前导1的个数。例如，整数7的二进制是0b111，其连续前导1的个数是3；整数6的二进制是0b110，其连续前导1的个数是2。虽然可以通过将整数转换为二进制字符串，然后查找第一个0的位置来解决，但这种方法涉及字符串操作，效率相对较低。本教程将介绍一种纯粹基于位操作的高效解决方案。

下表展示了一些整数及其连续前导1的数量：

位操作解决方案

核心思想是利用位反转（XOR操作）和Python整数的bit_length()方法。bit_length()方法返回表示一个整数所需的最小位数，不包括符号位和任何前导零。

核心函数

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()

登录后复制

原理解析

1. 获取原始位长度 (n.bit_length()): n.bit_length()确定了表示整数n所需的最小位数。这为我们提供了一个基准长度，例如，对于0b110，其bit_length()为3。
2. 创建全1掩码 (all_ones_mask): (1
3. 位反转 (n ^ all_ones_mask): 异或（XOR）操作是实现位反转的关键。当一个位与1进行XOR操作时，其值会反转（0变1，1变0）。例如：
   • 如果n = 0b110 (6)，all_ones_mask = 0b111 (7)。
   • inverted = 0b110 ^ 0b111 = 0b001 (1)。
   • 原始数字的前导1（11）变成了00。
4. 计算差值 (num_bits - inverted.bit_length()):
   • 当n的连续前导1被反转为0后，这些前导0将不再被inverted.bit_length()方法计入其长度。
   • 例如，n=0b110，num_bits=3。inverted=0b001，其bit_length()为1。
   • 那么，3 - 1 = 2，这正是0b110中连续前导1的数量。
   • 对于n=0b111，num_bits=3。inverted=0b000，其bit_length()为0。
   • 那么，3 - 0 = 3，这正是0b111中连续前导1的数量。

示例

for i in range(8):
    print(f"{i} {bin(i)}: {count_leading_ones(i)}")

登录后复制

输出结果：

立即学习“Python免费学习笔记（深入）”；

标签： python 代码可读性