You need to enable JavaScript to run this app. Python递归实现返回数字n二进制最长连续0的个数(需用&、>>)
优惠活动
大模型
产品
解决方案
定价
更多

Python递归实现返回数字n二进制最长连续0的个数(需用&、>>)

解题核心约束

先把题目硬性要求列清楚,避免走偏:

  • 必须采用递归实现,不能写循环逐位遍历
  • 位处理只能用&(按位与)、>>(右移),不能直接把整数转成二进制字符串数0
  • 输出是二进制表示(从最高位的1到最低位)中最长连续0的个数,比如44的二进制是101100,结果是2。
递归实现需要维护的状态

递归逐位扫描的时候,没法像循环那样随时回溯之前的扫描结果,所以需要把两个关键状态作为参数在递归层之间传递:

  • current_streak:当前正在统计的连续0的长度,碰到1就重置为0,碰到0就+1
  • max_streak:之前扫描过的位里,已经出现过的最长连续0的长度,每次更新current_streak后就和它比对取最大值
位运算的具体作用

两个强制要求的运算符刚好覆盖逐位判断和移位的需求:

  • num & 1:强制要求使用的按位与运算,取出当前数字的最低位值,是0还是1,用来判断要不要累计连续0长度
  • num >> 1:强制要求使用的右移运算,把数字的最低位移除,得到下一层递归要处理的数字,相当于逐位向更高位扫描,直到数字变成0,触发递归终止。
流程走查(以n=44为例)

按递归逻辑一步步跑,验证正确性:

  1. 初始调用:num=44(二进制101100),current_streak=0,max_streak=0
  2. 第一层判断:44 & 1 = 0 → current_streak更新为1,max_streak更新为1,num右移变成22(10110)
  3. 第二层判断:22 & 1 = 0 → current_streak更新为2,max_streak更新为2,num右移变成11(1011)
  4. 第三层判断:11 & 1 = 1 → current_streak重置为0,max_streak保持2,num右移变成5(101)
  5. 第四层判断:5 & 1 =1 → current_streak保持0,max_streak保持2,num右移变成2(10)
  6. 第五层判断:2 &1 =0 → current_streak更新为1,max_streak和1比还是2,num右移变成1(1)
  7. 第六层判断:1 &1 =1 → current_streak重置为0,max_streak保持2,num右移变成0,触发终止条件,返回max_streak=2,和示例结果完全一致。
参考实现代码
def longest_consecutive_zero(n: int) -> int:
    def recursive_scan(num: int, current_zero: int, max_zero: int) -> int:
        # 递归终止:所有有效位已经扫描完成
        if num == 0:
            return max_zero
        # 按位与取当前最低位
        if num & 1 == 0:
            new_current = current_zero + 1
            new_max = max(max_zero, new_current)
        else:
            # 碰到1,连续0计数清零
            new_current = 0
            new_max = max_zero
        # 右移一位,进入下一层递归
        return recursive_scan(num >> 1, new_current, new_max)
    
    # 边界处理:n=0时没有有效1位,最长连续0为0
    if n <= 0:
        return 0
    return recursive_scan(n, 0, 0)
常见踩坑提醒
  • 不要把Python整数的前导0算进去:因为递归终止条件是num==0,扫描范围只会从最低位到最高位的1,不会把无限长的前导0统计进去
  • 碰到1的时候一定要重置连续计数,不然会把两段不连续的0算成一段
  • 严格不要用字符串转换,不然不符合作业的考核要求

内容的提问来源于stack exchange,提问作者Raphaeliptv7

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.02 01:45:10