使用分治法反转比特位时遇TypeError错误的解决方法

问题重现 #

尝试用分治法反转比特位顺序，实现代码如下：

def reverseBits(n, p, q):
    if len(n) <= 1:
        return
    mid = (p+q)//2
    return reverseBits(n[mid+1:q+1], mid, q) + reverseBits(n[p:mid+1], p, mid)

调用代码：

n = list(str(10110))
print(reverseBits(n, 0, len(n)-1))

运行后触发错误：

TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

错误原因分析 #

1. 递归终止返回值错误：当len(n) <= 1时，函数直接return（无返回值，即返回None），递归到最底层时，两个子调用都会返回None，执行+操作自然报错。
2. 递归索引参数不匹配：切片后的子数组是新的列表，长度和原数组不同，此时传入原数组的mid、q等索引完全无效，会导致子数组的递归逻辑混乱。

修复方案 #

修正点说明 #

• 终止条件返回当前子数组：当子数组长度≤1时，无需反转，直接返回该数组。
• 重新计算子数组的索引：基于原数组的索引范围计算子数组边界，递归时传入对应的原数组索引，而非切片后的新数组索引。
• 调整拼接顺序：要实现整体反转，需先反转右半部分，再反转左半部分，最后将反转后的右半部分放在前面，左半部分放在后面。

修复后的代码 #

def reverseBits(n, p, q):
    # 子数组长度<=1时，直接返回该子数组切片
    if q - p + 1 <= 1:
        return n[p:q+1]
    mid = (p + q) // 2
    # 递归反转右半部分和左半部分
    reversed_right = reverseBits(n, mid + 1, q)
    reversed_left = reverseBits(n, p, mid)
    # 拼接反转后的右半和左半，得到整体反转结果
    return reversed_right + reversed_left

调用验证 #

n = list(str(10110))
result = reverseBits(n, 0, len(n)-1)
print(''.join(result))  # 输出：01101

补充优化（可选） #

如果不想依赖索引参数，也可以简化为仅接收数组的版本，更符合分治的直观逻辑：

def reverseBits(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return reverseBits(arr[mid:]) + reverseBits(arr[:mid])

n = list(str(10110))
print(''.join(reverseBits(n)))  # 输出：01101

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