C++로 숫자의 이진 표현에서 선행 0 개수 구하기

문제 개요

주어진 숫자의 이진(binary) 표현에서 선행 0(leading zeroes)의 개수를 구하는 문제입니다. 이때 전체 비트 수는 32비트라고 가정합니다.

예를 들어 살펴보겠습니다.

입력

5

출력

29

숫자 5의 이진 표현은 00000...00101입니다. 실제로 값이 채워진 비트는 맨 뒤의 3개뿐이므로, 나머지 앞부분에 해당하는 선행 0은 총 29개입니다.

알고리즘

• 숫자 n을 초기화합니다.
• n의 이진 표현을 구합니다.
• 전체 비트 수(32)에서 n의 이진 표현 길이를 뺍니다.
• 계산된 결과를 반환합니다.

구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int getLeadingZeroesCount(unsigned int n) {
    int totalBits = sizeof(n) * 8;
    string binary = "";
    while (n) {
        int remainder = n % 2;
        if (remainder || binary.length() > 0) {
            binary += remainder;
        }
        n /= 2;
    }
    return totalBits - binary.length();
}
int main() {
    int n = 101;
    cout << getLeadingZeroesCount(n) << endl;
    return 0;
}

코드 설명

sizeof(n) * 8을 사용해 unsigned int 타입의 전체 비트 수인 32를 구합니다. 그다음 반복문을 통해 n을 2로 나누면서 각 자리의 나머지를 문자열에 추가하여 이진 표현을 만듭니다. 마지막으로 전체 비트 수에서 유효한 이진 자릿수를 빼면 선행 0의 개수가 됩니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

25

예제 코드에서는 n을 101로 설정했습니다. 101의 이진 표현은 1100101로 유효 비트가 7개이므로, 32 - 7 = 25개의 선행 0이 계산됩니다. 만약 n을 5로 설정하면 이진 표현이 101로 3비트이기 때문에 결과는 29가 됩니다.