C++로 숫자가 교대 비트 패턴을 갖는지 확인하기

문제 개요

정수 n이 주어졌을 때, 이 수의 이진수 표현이 교대 패턴(alternating pattern), 즉 101010…과 같은 형태를 가지고 있는지 확인하는 문제입니다.

O(1) 접근 방식의 핵심 아이디어

가장 먼저 num = n XOR (n >> 1)을 계산합니다. 만약 n의 비트가 101010…처럼 번갈아 나타난다면, n을 오른쪽으로 한 비트 시프트한 값과 XOR 연산을 수행한 결과인 num의 모든 비트가 1이 됩니다.

따라서 문제는 "num의 모든 비트가 1인가?"를 확인하는 것으로 단순화됩니다. 모든 비트가 1로 설정된 수는 2^k - 1 형태(예: 1, 3, 7, 15, 31…)이며, 이를 확인하는 방법은 (num + 1) & num == 0인지 검사하는 것입니다. 결과가 0이라면 num + 1은 2의 거듭제곱이고, num은 모든 비트가 1로 채워진 수임을 알 수 있습니다.

예제 코드

#include <iostream>
#include <algorithm>
using namespace std;

// 모든 비트가 1로 설정되어 있는지 확인하는 함수
bool isAllBitSet(int n){
    // n이 2^k - 1 형태이면 (n + 1) & n 의 결과는 0
    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

동작 과정 상세 분석

예제에서 사용한 숫자 42를 직접 살펴보겠습니다. 42의 이진수 표현은 101010으로, 완벽한 교대 패턴입니다.

n = 42 → 이진수: 101010
n >> 1 = 21 → 이진수: 010101
n XOR (n >> 1) = 63 → 이진수: 111111

XOR 연산 결과인 63은 모든 비트가 1인 수입니다. 따라서 hasAlternatePattern 함수는 true를 반환하고, 해당 숫자가 교대 패턴을 가진다는 메시지가 출력됩니다.

시간 및 공간 복잡도