C++에서 이진 표현이 모두 1인 숫자 개수 세기

개요

양의 정수 N이 주어졌을 때, N 이하의 수 중에서 이진 표현이 모두 1로만 이루어진 숫자가 몇 개 있는지 구하는 것이 이 글의 목표입니다. 예를 들어 1은 이진수로 1, 3은 11, 7은 111, 15는 1111처럼 표현되는 숫자들입니다.

이런 숫자들을 자세히 보면 모두 2ⁱ − 1 형태라는 공통점이 있습니다. 여기서 지수 i는 1부터 시작합니다. 따라서 N 이하에서 이러한 숫자를 찾으려면 2ⁱ − 1 ≤ N 인지만 확인하고, 조건을 만족할 때마다 카운트를 증가시키면 됩니다.

예제로 이해하기

입력: N = 15
출력: 이진 표현이 모두 1인 숫자의 개수 : 4
설명: 조건을 만족하는 숫자는 1, 3, 7, 15입니다.

입력: N = 50
출력: 이진 표현이 모두 1인 숫자의 개수 : 5
설명: 조건을 만족하는 숫자는 1, 3, 7, 15, 31입니다.

프로그램의 접근 방식

양의 정수 N을 입력받습니다.
allOnes(int n) 함수는 n을 입력으로 받아, 이진 표현이 모두 1인 숫자의 개수를 반환합니다.
해당 숫자를 세기 위한 변수 count를 0으로 초기화합니다.
for 루프를 사용해 i = 1부터 i ≤ n까지 반복합니다.
각 i에 대해 pow(2, i) − 1이 n보다 작거나 같으면 count를 1 증가시킵니다.
for 루프가 종료되면 count를 결과로 반환합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
int allOnes(int n){
    int count = 0;
    for(int i = 1; i <= n; i++){
        if(n >= pow(2, i) - 1){
            count++;
        }
    }
    return count;
}
int main(){
    int N = 23;
    cout << endl << "Number having all 1's in binary : " << allOnes(N);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Number having all 1's in binary : 4

N = 23일 때 조건을 만족하는 숫자는 1, 3, 7, 15의 네 개이며, 다음 값인 31은 23보다 크므로 제외됩니다.

효율성 개선 팁

위 코드는 단순하게 i를 1부터 n까지 모두 순회하지만, 사실 그럴 필요가 없습니다. 2ⁱ − 1은 지수적으로 증가하기 때문에 i가 log₂(N + 1)을 넘는 순간부터는 조건을 절대 만족하지 않습니다. 따라서 반복 범위를 줄이면 N이 아무리 커도 약 30~60회 정도의 반복만으로 빠르게 답을 구할 수 있으며, 부동소수점 오차를 피하고 싶다면 pow() 대신 비트 시프트 연산자 (1LL << i) - 1을 사용하는 것도 좋은 방법입니다.