如何高效查找百万位及以上数字中连续1比特的最大个数？

以数字123456789为例，它的二进制是111010110111100110100010101，其中连续1比特的最大数量是4。针对百万位甚至更长的数字，有人设计了如下代码：

def onebits(n):
    ctr = 0
    while n:
        n &= n >> 1
        ctr += 1
    return ctr

原代码原理与局限 #

n &= n >> 1操作会同时截断每段连续1比特的最高位，重复执行直到所有连续1消失，操作次数就是最长连续1的数量。比如二进制数11101011的处理过程：

11101011 (初始值)
->  1100001
->   100000
->        0

共执行3步，对应最长连续1的数量为3。这种方法在处理连续1较短的随机数字时速度很快（对应基准测试中的Kelly3），但如果数字存在超长连续1段，时间复杂度会达到O(b²)（b为数字的比特长度），性能会急剧下降。

更优解法：分治式位运算合并 #

可以采用分治思路的位运算实现O(log b)时间复杂度的解法，无论数字是否存在长连续1，效率都稳定可控。核心是通过逐步合并相邻区间的连续1计数，最终得到最大值：

def max_consecutive_ones(n):
    # 计算每两位的连续1长度
    n = n - ((n >> 1) & 0x5555555555555555)
    # 合并相邻两位结果，得到每四位的连续1长度
    n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
    # 合并每四位结果，得到每八位的连续1长度
    n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f
    # 合并每八位结果
    n = n + (n >> 8)
    # 合并每十六位结果
    n = n + (n >> 16)
    # 合并每三十二位结果（针对64位数字，更长数字可继续扩展）
    n = n + (n >> 32)
    # 最终结果存储在最低8位中
    return n & 0xff

解法对比 #

• 原方法：随机短连续1场景下表现优秀，但长连续1场景时间复杂度退化为O(b²)，无法高效处理百万位数字。
• 分治位运算解法：固定O(log b)时间复杂度，仅需常数次位运算操作，无论数字结构如何，都能快速得到结果，完美适配超长数字的处理需求。
• 逐位遍历解法：时间复杂度O(b)，实现简单，但需要遍历所有比特位，效率比分治法低，不过仍优于原方法的最坏情况。

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