A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.
For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.
Write a function:
function solution(N);
that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.
For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..2,147,483,647].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
기본
input : 37 입력된 값 N을 2진수로 변경하였을 때 1과 1 사이의 가장 많은 0의 수를 계산하는 문제로 N을 2로 나누어 떨어지는 경우는 0으로 나누어 지지 않는 경우는 1이기 때문에 나머지가 0인 경우 숫자를 카운트
10진수 37의 경우 2진수로 100101이며 2로 나눈 값은 10진수로 18과 나머지 1, 2진수로 10010과 나머지 1이 된다.
2로 나누어 지지 않는 경우 나머지는 2진수의 가장 오른쪽 1이고 이 후 2로 나누어지는 경우 2진수에서 가장 오른쪽에 다시 1이 올 때까지 0의 갯수를 카운트한다.
기본 cnt는 0이기 때문에 2진수로 1, 10, 100 등과 같이 1이 하나만 존재하는 수는 cnt의 값이 증가하지 않는다.
추가
2진수 1000100000과 같이 끝이 1로 끝나지 않는 2진수는 결국 10001만 필요하고 100000은 오른족이 1이 아니기 때문에 숫자를 카운트 할 필요가 없기 때문에 right shift연산을 한다.
2진수 2는 10이기 때문에 1000100000가 10001이 될 때까지 right shift를 하여 10001을 만든다. 이 부분은 shift연산이 아닌 N/2연산을 통해 2진수 10으로 나누어도 동일한 결과를 얻을 수 있다.
추가2 부분을 나누기로 할 경우 javascript는 모든 숫자가 double형이기 때문에 N을 2로 나눈 후 소수점을 버린다.
functionsolution(N) { // write your code in JavaScript (Node.js 8.9.4) var cnt = 0; var max = -1; //추가1 while (N % 2 == 0) { N = N 1; } while (N 0) { if (N % 2 == 0) { cnt++; } else { max = Math.max(cnt, max); cnt = 0; } N = N 1; //추가2 } return max; }
