C++에서 1의 보수와 동일한 이전 숫자

이 문제에서는 정수 n이 주어집니다. 우리의 임무는 앞의 숫자가 숫자의 1의 보수와 같은지 날씨를 확인하는 것입니다.

문제를 이해하기 위해 몇 가지 예를 들어보겠습니다.

Input: 12
Output: No
Explanation: (12)10 = (1100)2
Preceding number 11 = (1011)2
1’s complement of 12 = (0011)2
Input: 4
Output: Yes
Explanation: 4 = (100)2
Preceding number 3 = (011)2
1’s complement of 12 = (011)2

이 문제를 해결하기 위해 이전 숫자와 숫자의 1의 보수를 비교하는 간단한 접근 방식을 사용할 수 있습니다.

이 접근 방식은 간단하지만 공간과 시간을 소모합니다. 시간 복잡도:O(n)

효과적인 솔루션은 문제를 해결하기 위해 추구하는 일반적인 방법을 사용하는 것일 수 있습니다. 여기서 2의 거듭제곱인 숫자만 조건을 만족합니다. 즉, 이전 숫자는 1의 보수와 같습니다.

솔루션 구현을 보여주는 프로그램

예시

#include <iostream>
using namespace std;
bool sameBits(unsigned long int n){
   if ((n & (n - 1)) == 0)
      return true;
   return false;
}
int main(){
   unsigned long int n = 64;
   if(sameBits(n))
      cout<<"Both are the same";
   else
      cout<<"Both aren't the same";
   return 0;
}

출력

Both are the same