1. Algorithm

To solve the problem we will need to divide the task into a two of parts. First, find binary representation of the number and save its representation as string. Second part will be responsible and calculate the biggest binary gap and return its size.

1.1. Binary representation

There is many ways to find binary representation for the given number. Here I will demonstrate two of them.

1.1. a) First one uses modulo and dividing to find the binary representation of the number. Exact explanation can be found in the comments of the pseudo-code bellow.

          
void intToBin(int n, char binary[], int binary_size){
    // Set index initial position to last element
    int pos = binary_size - 1;
    
    // Iterate until n > 0
    while(n > 0){
    	// Check if n is dividable by 2 and set respectively
        // '0' if it is and '1' if it isn't
        binary[pos] = n % 2 ? '1' : '0';
        // Divide n by 2 to calculate next position
        n /= 2;
        // Decrease index by one
        pos -= 1;
    }
}
			
      	

1.1. b) Second method uses bitwise AND operator and checks whenever given bit in the number is set or not.

          
void intToBin(int n, char binary[], int binary_size){
    // Set index initial position to last element
    int pos = binary_size - 1;
    
    // Iterate through the list from end of it
    for(int i=pos; i >= 0; i--){
        // Each iteration binary move 1 by i places and
        // compare with given number n by AND-ing them together
        binary[pos - i] = n & 1 << i ? '1' : '0';
    }
}
			
      	

For the implementation, we will use example 1.1 a), as it's much faster than the bit checks(1.2).

1.2. Count size of binary gap

The easiest way to calculate the binary gap is to iterate through the representation of the binary number and count 0s placed between 1s.

        	
int calcGap(char bin[], int bin_size){
    int max_gap=0, tmp_gap=0;
    bool start = false;

    // Iterate through the binary representation of number
    for(int i=0; i < bin_size; i++){
        // If actual number is '1', then check if previously
        // calculated gap is bigger than the one now,
        // if it is replace max_gap with new result.
        if(bin[i] == '1'){
            if(start){
                max_gap = max_gap > tmp_gap ? max_gap : tmp_gap;
                tmp_gap = 0;
            }else{
            	// This will be executed when first '1' found in string.
            	start = true;
            }
        }else if(start){
            // Variable start is set to positive number
            // when '1' is detected. That means, binary number
            // started and from this moment we should count '0's.
            ++tmp_gap;
        }
    }
    
    return gap;
}
            
        

1. Implementation language: C

        	
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void intToBin(int n, char* binary, int binary_size){
    int pos = binary_size - 1;
    
    while(n > 0){
        binary[pos] = n % 2 ? '1' : '0';
        n /= 2;
        pos -= 1;
    }
}

int calcGap(char* bin, int bin_size){
    int i, start=0, gap=0, tmp_gap=0;

    for(i=0; i<bin_size; i++){
        if(bin[i] == '1'){
            if(start++){
                gap = gap > tmp_gap ? gap : tmp_gap;
                tmp_gap = 0;
            }
        }else if(start){
            ++tmp_gap;
        }
    }	
    
    return gap;
}

int solution(int N) {
    int i, n, bin_size = (sizeof(int) * 8);
    char *bin = (char *)malloc(bin_size);
    if(bin==NULL){
        exit(0);
    }
    memset(bin, '0', bin_size);
    
    intToBin(N, bin, bin_size);
    int gap = calcGap(bin, bin_size);
    free(bin);
    
    return gap;
}

// Comment code below before running in Codility.
// /*
int main(){
    int n;
    
    printf("Enter number to find its binary gap: ");
    scanf("%d", &n);
    
    printf("Calculated gap: %d\n", solution(n));

    return 0;
}
// */
            
        

2. Implementation language: C++11

Unfortunately Codility can compile C++ code up to 0x11. The code below can be optimized with C++14 by replacing functions return type by auto and std::unique_ptr by std::make_unique.

        	
#include <iostream>
#include <memory>
#include <string>

const auto INT_SIZE = sizeof(int)*8;

std::unique_ptr<std::string> numToStr(int n){
    std::unique_ptr<std::string> bin(new std::string(INT_SIZE, '0'));
    auto pos = INT_SIZE-1;
    
    while(n > 0){
        if(n % 2){
            bin->operator[](pos) = '1';
        }
        n /= 2;
        --pos;
    }

    return bin;
}

int calcGap(const std::unique_ptr<std::string> &bin){
    auto pos = bin->find_first_of('1');
    if(pos == -1){
        return 0;    
    }
    auto max_gap = 0, tmp_gap = 0;

    for(int i=pos+1, len=bin->size(); iat(i) == '1'){
            max_gap = max_gap > tmp_gap ? max_gap : tmp_gap;
            tmp_gap = 0;
        }else{
            ++tmp_gap;
        }
    }
    
    return max_gap;
}

int solution(int N) {
    auto bin = numToStr(N);
    return calcGap(bin);
}

// Comment code below before running in Codility.
// /*
int main(){
    int n;
    
    std::cout << "Enter number to find its binary gap: ";
    std::cin >> n;
    
    std::cout << "Calculated gap: " << solution(n);

    return 0;
}
// */
            
        

3. Implementation language: Python2.7

        	
#!/usr/bin/python

def intToBin(n):
    res = ''
    while(n > 0):
        res += '1' if n%2 else '0'
        n /= 2

    return res[::-1]
    
def calcGap(bin):
    started = False
    max_gap = 0
    tmp_gap = 0

    for c in bin:
        if c == '1':
            max_gap = max(max_gap, tmp_gap)
            tmp_gap = 0
        else:
            tmp_gap += 1
    
    return max_gap

def solution(N):
    bin = intToBin(N)
    return calcGap(bin)

# Comment code below before running in Codility.
# """
if __name__ == '__main__':
    n = raw_input("Enter number to find its binary gap: ")
    
    print "Calculated gap: %s" % solution(n);
# """