Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 설정된 비트 수가 하나 더 있는 다음 큰 정수

<시간/>

숫자 n이 주어지면 이진 표현에서 n보다 하나 더 많은 세트 비트를 사용하여 n보다 큰 숫자를 찾아야 합니다.

바이너리 표현에서 숫자 1을 세트 비트라고 합니다.

예를 들어 보겠습니다.

입력

124

출력

125

알고리즘

  • 숫자 n 초기화 .

  • 설정한 비트 수를 구하는 함수를 작성합니다.

  • n + 1을 사용하여 반복 변수를 초기화합니다. .

  • 무한 루프를 작성하십시오.

    • n보다 큰 숫자에 대해 설정된 비트 수 확인 .

    • 번호를 찾으면 반환하십시오.

구현

다음은 위의 알고리즘을 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