使用递归解决二进制间隔问题

1. 介绍

Binary Gap（二进制间隔） 是指一个正整数的二进制表示中，两个1之间最长的连续0的个数。例如数字 9 的二进制是 1001，两个1之间有两个0，所以它的 binary gap 是 2。

这个问题通常可以用迭代方式解决，本文将展示一种递归解法，帮助你从不同角度理解问题的本质。

2. 解法

2.1. 算法思路

我们需要从最低位开始，逐位检查数字的二进制表示。只有在遇到第一个1之后，才开始统计连续的0。因此，递归过程中需要维护三个状态：

number：当前处理的数字
foundFirstOne：是否已经遇到第一个1
numOfZeros：当前连续0的数量

每次递归逻辑如下：

取出最低位：使用 number % 2 得到当前位
如果是1：
- 递归调用时设置 foundFirstOne = true
- 同时重置 numOfZeros = 0
如果是0 且已找到第一个1：
- numOfZeros 加1
否则（0但还没找到第一个1）：
- 不统计，继续递归

最终返回当前统计的0和递归结果中的最大值。

2.2. 伪代码实现

以下是该递归算法的伪代码：

algorithm BinaryGap(Number, FoundFirstOne, NumOfZeros):
    // INPUT
    //   Number = The number to calculate binary gap for
    //   FoundFirstOne = The flag indicating whether we have found the first bit equal to one
    //   NumOfZeros = The number of consecutive zeros so far
    // OUTPUT
    //   Answer = Returns the answer to the binary gap problem
    if Number = 0:
        return 0
    CurrentBit <- Number mod 2
    if CurrentBit = 1:
        Answer <- BinaryGap(Number div 2, true, 0)
    else:
        if FoundFirstOne = True:
            Answer <- BinaryGap(Number div 2, true, NumOfZeros + 1)
        else:
            Answer <- BinaryGap(Number div 2, false, 0)
    return Maximum(Answer, NumOfZeros)

初始调用应传入原始数字、foundFirstOne = false、numOfZeros = 0

2.3. Java 实现

下面是一个 Java 语言的递归实现示例：

public class BinaryGap {

    public static int binaryGap(int number) {
        return binaryGapRecursive(number, false, 0);
    }

    private static int binaryGapRecursive(int number, boolean foundFirstOne, int numOfZeros) {
        if (number == 0) {
            return 0;
        }

        int currentBit = number % 2;

        if (currentBit == 1) {
            int result = binaryGapRecursive(number / 2, true, 0);
            return Math.max(result, numOfZeros);
        } else {
            if (foundFirstOne) {
                int result = binaryGapRecursive(number / 2, true, numOfZeros + 1);
                return Math.max(result, numOfZeros);
            } else {
                return binaryGapRecursive(number / 2, false, 0);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(binaryGap(9));  // 输出: 2
        System.out.println(binaryGap(529)); // 输出: 4
        System.out.println(binaryGap(20)); // 输出: 1
        System.out.println(binaryGap(15)); // 输出: 0
    }
}

2.4. 时间复杂度分析

✅ 时间复杂度：O(log n)
因为每次递归都将数字除以2，所以总共递归次数为 log₂N。

❌ 空间复杂度：O(log n)
由于递归栈的深度也是 log₂N，因此空间复杂度与时间复杂度相同。

3. 总结

本文介绍了使用递归方式解决 Binary Gap 问题的思路和实现。

通过递归逐位处理，模拟了迭代器的行为
使用三个参数清晰地维护递归过程中的状态
时间复杂度为 O(log n)，适合处理大整数

递归解法虽然不是最直观的，但它有助于训练逻辑思维和递归思维，是理解二进制处理的一个不错练习。如果你在面试或编码练习中遇到类似问题，不妨试试这种思路。

Persistence

REST

Security