Binary Gap exercise

Finding the largest gap between ones in a binary number makes for a great coding exercise.

Where is the state in this problem?

• We need to know if we’re in a line of zeros (or between ones) in the number.
• We need to count the zeros.
• We need to track the maximum count of zeros we’ve seen between ones in the whole number.

Examples: 9 - 1001 - Max number of zeros is 2. 1041 - 10000010001 - Max number of zeros is 5.

In order to solve this we need to iterate over bits in the number. When we encounter 1 we need to evaluate whether we’re inside a line of zeros. We conditionally set the new maximum or flag that we’re inside the line of zeros. In both cases we need to reset the counter. When we encounter 0 we just check whether we’re inside the line of zeros and increment the counter. At the end of the cycle we shift the bits to the right.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <algorithm>

int solution(int N) {
    int maximum = 0;
    int counter = 0;
    bool is_inside = false;
    
    while(N > 0) {
        if(N & 1) {
            if(is_inside) {
                maximum = std::max(maximum, counter);
            } else {
                is_inside = true;
            }
            counter = 0;
        } else {
            if(is_inside) {
                counter++;
            }
        }
        N >>= 1;
    }
    return maximum;
}