Lesson 99: BinaryGap (Binary Gap)

Lesson 99: BinaryGap
https://codility.com/programmers/lessons/14

Here is my first solution. It gives the 100% score.

I was wondering why the expected worst time complexity of this problem is O(log(N)). as 'int' is always 32 bit in this environment.

Yet, I guess it is because we can terminate the loop when there is no more binary gap can be found.

int solution(int N) 
{
    int max = 0;
    
    int mask = 0x80000000;

    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

And here is the version to terminate the loop when there is no more binary gap. This is the O(log(N)) version.

int solution(int N) 
{
    int max = 0;
    
    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N >> i) & 1;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N >> i);
        if (tmp == 0){
            break;
        }
        
        tmp = tmp & 1;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

And here is a shorter version.

int solution(int N) {
    
    int max = 0;
    int flg = 0;
    int cnt = 0;
    
    while (N > 0){
        if (N & 1 == 1){
            if (flg == 0){
                flg = 1;
            }
            else {
                max = max < cnt ? cnt : max;
            }
            cnt = 0;
        }
        else {
            cnt++;
        }
        N = N >> 1;
    }
    
    return max;
}