C++로 세트 비트가 하나 더 많은 다음 큰 정수 찾는 방법

문제 개요

하나의 정수 n이 주어졌을 때, n보다 크면서 이진수 표현에서 세트 비트(set bit)의 개수가 정확히 하나 더 많은 수를 찾는 것이 이 글의 목표입니다.

여기서 세트 비트란 이진수 표현에서 값이 1인 비트를 의미합니다.

예시

입력:

124

출력:

125

124의 이진 표현은 1111100으로 세트 비트가 5개입니다. 바로 다음 수인 125는 1111101로 세트 비트가 6개, 즉 하나 더 많으므로 정답이 됩니다.

알고리즘

1. 숫자 n을 초기화합니다.

2. 세트 비트의 개수를 세는 함수를 작성합니다.

3. 반복 변수를 n + 1로 초기화합니다.

4. 무한 루프를 실행합니다.

   • n보다 큰 각 수에 대해 세트 비트 개수를 확인합니다.

   • 세트 비트 개수가 n보다 정확히 하나 많은 수를 찾으면 해당 수를 반환합니다.

C++ 구현

위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
int getSetBitsCount(int n) {
   int count = 0;
   while (n) {
      if (n % 2 == 1) {
         count += 1;
      }
      n /= 2;
   }
   return count;
}
int getNextGreaterElementWithSameSetBits(int n) {
   int setBitsCount = getSetBitsCount(n);
   int i = n + 1;
   while (true) {
      if (setBitsCount + 1 == getSetBitsCount(i)) {
         return i;
      }
      i += 1;
   }
}
int main() {
   int n = 124;
   cout << getNextGreaterElementWithSameSetBits(n) << endl;
   return 0;
}

실행 결과

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

125

코드 설명

getSetBitsCount 함수는 주어진 수를 2로 계속 나누면서 나머지가 1일 때마다 카운트를 증가시켜, 전체 세트 비트의 개수를 반환합니다.

getNextGreaterElementWithSameSetBits 함수는 먼저 n의 세트 비트 개수를 구한 뒤, n+1부터 시작하여 조건(세트 비트가 하나 더 많음)을 만족하는 첫 번째 수를 찾을 때까지 차례대로 검사합니다. 조건을 만족하는 수를 발견하면 즉시 반환하고 종료됩니다.