자바스크립트로 이진수에서 인접한 1 사이의 가장 긴 거리 구하기

문제 소개

양의 정수 n이 주어졌을 때, n의 이진 표현에서 인접한 두 개의 1 사이에 존재하는 가장 긴 거리를 찾아 반환하는 자바스크립트 함수를 작성해야 합니다.

만약 인접한 두 개의 1이 존재하지 않는다면 0을 반환하면 됩니다.

인접과 거리의 정의

두 개의 1 사이에 0만 존재한다면(0이 하나도 없는 경우 포함) 이 둘은 '인접(adjacent)'하다고 정의합니다. 두 1 사이의 거리는 각 비트 위치 차이의 절댓값입니다. 예를 들어 이진수 "1001"에서 두 1의 거리는 3입니다.

예시로 이해하기

입력값이 22일 때 출력은 2가 되어야 합니다. 그 이유는 다음과 같습니다.

22의 이진 표현은 10110입니다.
오른쪽에서 첫 번째 1(위치 1)과 두 번째 1(위치 2)은 인접한 쌍이며, 거리는 1입니다.
두 번째 1(위치 2)과 세 번째 1(위치 4) 역시 사이에 0만 있으므로 인접한 쌍이며, 거리는 2입니다.
따라서 답은 두 거리 중 더 큰 값인 2입니다.

단, 가장 왼쪽의 1과 가장 오른쪽의 1은 그 사이에 또 다른 1이 끼어 있기 때문에 인접한 쌍으로 간주하지 않습니다.

해결 접근 방식

이 문제는 비트 시프트 연산을 활용하면 간단하게 해결할 수 있습니다. 정수의 각 비트를 오른쪽부터 한 칸씩 확인하면서, 1을 발견할 때마다 직전에 발견한 1의 위치와의 거리를 계산하고 그중 최댓값을 갱신하는 방식입니다.

구현 코드

const num = 22;

const binaryGap = (num = 1) => {
    let last = -1; // 마지막으로 발견한 1의 비트 위치
    let ans = 0;   // 최대 거리

    // 모든 비트를 순회하며 확인
    for (let i = 0; i < 32; i++) {
        // 현재 비트가 1인지 검사
        if (((num >> i) & 1) === 1) {
            // 이전에 1을 발견한 적이 있다면 거리를 계산해 최댓값 갱신
            if (last >= 0) {
                ans = Math.max(ans, i - last);
            }
            last = i;
        }
    }
    return ans;
};

console.log(binaryGap(num)); // 2

코드 동작 원리

last 변수: 가장 최근에 발견한 1의 비트 위치를 저장합니다. 아직 1을 발견하지 못한 상태임을 나타내기 위해 초기값은 -1로 설정합니다.
비트 검사: (num >> i) & 1 표현식은 num을 i비트만큼 오른쪽으로 시프트한 뒤, 가장 오른쪽 비트가 1인지 확인합니다.
거리 계산: 현재 비트가 1이고 이전에 발견한 1이 있다면, 현재 위치 i에서 last를 뺀 값이 두 1 사이의 거리이며, 기존 최댓값보다 크면 갱신합니다.
32비트 순회: 일반적인 양의 정수는 32비트 범위 내에서 표현되므로 반복문을 0부터 31까지 수행하면 충분합니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.