숫자에 대체 패턴의 비트가 있는지 확인 - C++의 Set-2 O(1) 접근 방식

정수 n이 있다고 가정합시다. 문제는 이 정수가 이진법에 상응하는 대체 패턴을 가지고 있는지 여부를 확인하는 것입니다. 대체 패턴은 101010…을 의미합니다.

접근 방식은 다음과 같습니다. num =n XOR(n>> 1)을 계산합니다. 이제 num의 모든 비트가 1이면 num에 교대 패턴이 있습니다.

예시

#include <iostream>
#include <algorithm>
using namespace std;
bool isAllBitSet(int n){
   if (((n + 1) & n) == 0)
      return true;
   return false;
}
bool hasAlternatePattern(unsigned int n) {
   unsigned int num = n ^ (n >> 1);
   return isAllBitSet(num);
}
int main() {
   unsigned int number = 42;
   if(hasAlternatePattern(number))
      cout << "Has alternating pattern";
   else
      cout << "Has no alternating pattern";
}

출력

Has alternating pattern