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

1. Introduction

The binary gap of a number is defined as the maximum number of consecutive zeros that occur between two ones in the binary representation of the number. This problem can be solved iteratively, but in this article, we’ll present a recursive solution.

2. Solution

2.1. Algorithm

Let’s think about the problem. First, we need to find a way to extract the bits of the number, bit by bit. Next, we can notice that only when we find the first bit that is equal to one can we then start counting the number of consecutive zeros. The way of doing this is by simply passing along three variables:

Number: the number we are solving this problem for
FoundFirstOne: a boolean variable that is set to true once we find the first active bit
NumOfZeros: the number of consecutive zeros so far

To extract the least significant bit from a number, we can take its remainder after dividing it by 2. Similarly, to remove the least significant bit from the number, we should divide it by 2. As a result, every time we extract a bit from the number, there are two options:

If the extracted bit equals one, we should call the algorithm recursively after dividing the number by 2. Also, we should set FoundFirstOne to true (in case it wasn’t set yet). Finally, we should set NumOfZeros to zero because currently, we don’t have any consecutive zeros. Also, we should start counting again in case the next bit equals zero.
If the extracted bit equals zero, we should also call the algorithm recursively after dividing the number by 2. However, in this case, we will not change the value of FoundFirstOne. Also, we should increase NumOfZeros by one only if FoundFirstOne equals true.

In each step, we’ll return the maximum between NumOfZeros and the value returned from the recursive call. However, if this number equals zero, then the algorithm should immediately return zero, indicating that the last bit was one and this call didn’t find any consecutive zeros.

2.2. Pseudocode

The idea behind the algorithm we just described is that we can only start counting consecutive zeros after we find the first one-bit. Once the first one-bit is found, we will either increase the number of consecutive zeros by one or set it to zero in case the current bit equals one. Once the recursive call is finished, the answer will be either the value found recursively or the number of consecutive zeros we have so far.

Let’s see the pseudocode for our recursive algorithm:

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)

The initial call of this algorithm should pass the number, set FoundFirstOne to false, and set the value of NumOfZeros to zero.

2.3. Complexity

The complexity of our recursive algorithm is O(Log2N) because the algorithm only makes one recursive call, which divides the number by 2. This means that the algorithm will make a total of Log2N steps.

3. Conclusion

In this article, we described a recursive algorithm for solving the binary gap problem.

First, we described how the algorithm works. Then, we presented the pseudocode for our algorithm, and finally, we presented the algorithm’s complexity.

Persistence

REST