C++에서 숫자의 설정된 비트와 설정되지 않은 비트 개수가 같은지 확인하는 방법

이번 글에서는 어떤 숫자의 이진 표현에서 설정된 비트(set bit, 1)와 설정되지 않은 비트(unset bit, 0)의 개수가 서로 같은지 확인하는 방법을 알아보겠습니다.

예를 들어 숫자 12의 이진 표현은 1100입니다. 여기에는 1이 두 개, 0이 두 개 있으므로 두 종류의 비트 개수가 동일합니다.

접근 방법

알고리즘은 매우 간단합니다. 숫자의 각 비트를 하나씩 검사하면서, 해당 비트가 1이면 set_bit_count를 증가시키고, 0이면 unset_bit_count를 증가시킵니다. 모든 비트를 확인한 후 두 카운트가 같으면 true를, 그렇지 않으면 false를 반환합니다.

비트를 검사할 때는 비트 AND 연산(&)과 오른쪽 시프트 연산(>>)을 활용합니다. n & 1로 최하위 비트를 확인한 뒤, n을 오른쪽으로 한 칸 시프트하여 다음 비트를 검사합니다. 이 과정은 n이 0이 될 때까지 반복됩니다.

예제 코드

#include <iostream>
using namespace std;
bool hasSameSetUnset(int n) {
    int set_count = 0, unset_count = 0;
    while(n){
        if((n & 1) == 1){
            set_count++;
        }else{
            unset_count++;
        }
        n = n >> 1; // 오른쪽으로 시프트
    }
    if(set_count == unset_count)
        return true;
    return false;
}
int main() {
    int num = 35; // 100011
    if(hasSameSetUnset(num)){
        cout << "Has same set, unset bits";
    }else{
        cout << "Not same number of set, unset bits";
    }
}

실행 결과

Has same set, unset bits

숫자 35는 이진수로 100011이며, 1이 세 개, 0이 세 개이므로 설정된 비트와 설정되지 않은 비트의 개수가 같습니다. 따라서 위 프로그램은 true를 반환하고 "Has same set, unset bits"라는 메시지를 출력합니다.

시간 및 공간 복잡도

이 알고리즘은 숫자의 비트 길이만큼 반복하므로 시간 복잡도는 O(log n)입니다. 추가로 사용하는 메모리가 없으므로 공간 복잡도는 O(1)입니다.