[codility] BinaryGap

정수 N을 이진수로 나타냈을 때, 양쪽에 1이 있고 모든 원소가 0인 부분 리스트들 중 가장 긴 것의 길이를 구하는 문제.

N이 10010000와 같은 꼴일 때, 오른쪽에 1이 없는 경우를 제외하기 위해 N이 홀수가 될 때 까지 나누어준다. (10010000 -> 1001)

그 후, 부분 리스트들 중 가장 긴 것을 선택한다. N이 1보다 작다면 더 이상 왼쪽에 1이 있어야 한다는 조건을 만족할 수 없으므로 탐색을 종료한다.

cpp code

int solution(int N) {
    int ans = 0, len = 0;
    while ((N & 1) == 0) N /= 2;
    while (N) {
        if ((N & 1) == 0) len++;
        else {
            ans = max(ans, len);
            len = 0;
        }
        N /= 2;
    }
    return ans;
}