C++로 정수의 이진수가 교대 패턴(1010...)인지 확인하는 방법

정수 n이 주어졌을 때, 이 수의 이진수 표현이 교대 패턴(alternate pattern)을 가지는지 확인하는 문제를 살펴보겠습니다. 교대 패턴이란 101010...처럼 0과 1이 번갈아 나타나는 비트 배열을 의미합니다. 예를 들어 10진수 42의 이진 표현은 101010이므로 교대 패턴을 가진다고 볼 수 있습니다.

접근 방법

풀이 아이디어는 매우 직관적입니다. 이진수의 각 비트를 하나씩 검사하면서 인접한 두 비트를 비교하고, 두 비트가 같으면 즉시 false를 반환합니다. 끝까지 검사하는 동안 인접한 비트가 한 번도 같지 않았다면 true를 반환합니다.

구현에서는 n % 2로 최하위 비트를 추출하고, n / 2로 값을 줄여가며(오른쪽 시프트와 동일) 모든 비트를 순차적으로 확인합니다.

예제 코드

#include <iostream>
using namespace std;

bool hasAlternatePattern(unsigned int n) {
    int previous = n % 2;  // 최하위 비트를 이전 비트로 저장
    n = n / 2;
    while (n > 0) {
        int current = n % 2;  // 현재 비트 추출
        if (current == previous)  // 현재 비트가 이전 비트와 같으면
            return false;  // 교대 패턴이 아님
        previous = current;
        n = n / 2;
    }
    return true;
}

int main() {
    unsigned int number = 42;
    if (hasAlternatePattern(number))
        cout << "교대 패턴을 가집니다";
    else
        cout << "교대 패턴을 가지지 않습니다";
}

출력 결과

교대 패턴을 가집니다

42는 이진수로 101010이며, 모든 인접 비트가 서로 다르기 때문에 교대 패턴을 가지는 것으로 판별됩니다. 이 알고리즘은 비트 개수만큼 반복하므로 시간 복잡도는 O(log n)이며, 추가 메모리 없이 비트 연산만으로 해결할 수 있는 효율적인 방법입니다.