Python递归实现返回数字n二进制最长连续0的个数(需用&、>>)
解题核心约束
先把题目硬性要求列清楚,避免走偏:
- 必须采用递归实现,不能写循环逐位遍历
- 位处理只能用
&(按位与)、>>(右移),不能直接把整数转成二进制字符串数0 - 输出是二进制表示(从最高位的1到最低位)中最长连续0的个数,比如44的二进制是101100,结果是2。
递归实现需要维护的状态
递归逐位扫描的时候,没法像循环那样随时回溯之前的扫描结果,所以需要把两个关键状态作为参数在递归层之间传递:
current_streak:当前正在统计的连续0的长度,碰到1就重置为0,碰到0就+1max_streak:之前扫描过的位里,已经出现过的最长连续0的长度,每次更新current_streak后就和它比对取最大值
位运算的具体作用
两个强制要求的运算符刚好覆盖逐位判断和移位的需求:
num & 1:强制要求使用的按位与运算,取出当前数字的最低位值,是0还是1,用来判断要不要累计连续0长度num >> 1:强制要求使用的右移运算,把数字的最低位移除,得到下一层递归要处理的数字,相当于逐位向更高位扫描,直到数字变成0,触发递归终止。
流程走查(以n=44为例)
按递归逻辑一步步跑,验证正确性:
- 初始调用:num=44(二进制101100),current_streak=0,max_streak=0
- 第一层判断:
44 & 1 = 0→ current_streak更新为1,max_streak更新为1,num右移变成22(10110) - 第二层判断:
22 & 1 = 0→ current_streak更新为2,max_streak更新为2,num右移变成11(1011) - 第三层判断:
11 & 1 = 1→ current_streak重置为0,max_streak保持2,num右移变成5(101) - 第四层判断:
5 & 1 =1→ current_streak保持0,max_streak保持2,num右移变成2(10) - 第五层判断:
2 &1 =0→ current_streak更新为1,max_streak和1比还是2,num右移变成1(1) - 第六层判断:
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
相关产品推荐
相关产品推荐

