C++에서 숫자가 희소(sparse) 수인지 확인하는 방법

이번 글에서는 주어진 숫자가 희소 수(Sparse Number)인지 아닌지 판별하는 방법을 알아보겠습니다.

희소 수란 무엇인가?

희소 수는 숫자의 이진수 표현에서 연속된 두 개 이상의 1이 존재하지 않는 숫자를 의미합니다.

예를 들어 숫자 72의 이진수 표현은 01001000입니다. 이 표현을 살펴보면 연속해서 나타나는 1이 전혀 없으므로, 72는 희소 수입니다.

판별 원리

숫자가 희소 수인지 확인하는 방법은 매우 간단하며 비트 연산만으로 해결할 수 있습니다.

1. 주어진 숫자를 n이라고 합니다.
2. n을 오른쪽으로 1비트 시프트한 값(n >> 1)과 원래 값 n에 대해 비트 AND(&) 연산을 수행합니다.
3. 연산 결과가 0이면 해당 숫자는 희소 수이고, 그렇지 않으면 희소 수가 아닙니다.

동작 원리: 만약 이진수 표현에 연속된 1이 존재한다면, n과 n을 오른쪽으로 한 비트 시프트한 값에서 같은 자리에 1이 겹치게 되므로 AND 연산 결과가 0이 아니게 됩니다. 반대로 연속된 1이 없다면 모든 자리에서 겹치는 1이 없어 결과가 0이 됩니다.

C++ 구현 예제

#include <iostream>
using namespace std;

bool isSparseNumber(int n) {
   int res = n & (n >> 1);
   if(res == 0)
      return true;
   return false;
}

int main() {
   int num = 72;
   if(isSparseNumber(num)){
      cout << "This is sparse number";
   } else {
      cout << "This is not sparse number";
   }
}

출력 결과

This is sparse number

복잡도 분석

• 시간 복잡도: O(1) — 단일 비트 시프트와 AND 연산만 수행하므로 상수 시간에 처리됩니다.
• 공간 복잡도: O(1) — 추가적인 메모리 사용이 없습니다.

마무리

이처럼 비트 시프트와 AND 연산을 조합하면 별도의 루프나 이진수 변환 없이 O(1) 시간 안에 희소 수 여부를 손쉽게 판별할 수 있습니다. 비트 조작 기법을 활용한 대표적인 최적화 예시이므로 코딩 인터뷰에서도 유용하게 활용될 수 있습니다.