C++로 이블 넘버(Evil Number) 판별하기 – 예제 코드와 함께 배우는 방법

이블 넘버(Evil Number)와 오디어스 넘버(Odious Number)란?

이번 문제에서는 하나의 숫자 N이 주어졌을 때, 해당 숫자가 이블 넘버(Evil Number)인지 오디어스 넘버(Odious Number)인지 판별하는 것이 목표입니다.

이블 넘버(Evil Number)

2진수 표현에서 1의 개수가 짝수인 양의 정수를 말합니다.

예시: 5, 17

오디어스 넘버(Odious Number)

2진수 표현에서 1의 개수가 홀수인 양의 정수를 말합니다.

예시: 4, 6

예제로 이해하기

입력: N = 65

출력: 이블 넘버

설명:

65의 2진수 표현은 1000001이며, 여기에는 1이 두 개 포함되어 있습니다. 1의 개수가 짝수이므로 65는 이블 넘버입니다.

문제 해결 접근 방법

가장 간단한 해결 방법은 다음과 같습니다.

주어진 숫자를 2진수로 변환한다.
2진수 표현에서 1의 개수를 센다.
1의 개수가 짝수이면 이블 넘버, 홀수이면 오디어스 넘버로 판별한다.

반복적인 나눗셈과 나머지 연산 또는 비트 연산을 활용하면 손쉽게 구현할 수 있습니다.

C++ 구현 코드

#include <iostream>
using namespace std;

// 이블 넘버 판별 함수
int isEvilNumber(int n) {

    int count = 0;
    while (n != 0) {
        int r = n % 2;   // 마지막 비트 추출
        if(r == 1)
            count++;     // 1의 개수 카운트
        n = n / 2;       // 오른쪽 시프트
    }

    if (count % 2 == 0)
        return 1;   // 짝수개 → 이블 넘버
    else
        return 0;   // 홀수개 → 오디어스 넘버
}

int main(void)
{
    int num = 2049;
    if (isEvilNumber(num))
        cout<<"숫자 "<<num<<"은(는) 이블 넘버(Evil Number)입니다";
    else
        cout<<"숫자 "<<num<<"은(는) 오디어스 넘버(Odious Number)입니다";
    return 0;
}

실행 결과

숫자 2049은(는) 이블 넘버(Evil Number)입니다

비트 연산으로 더 간단하게 구현하기

GCC 계열 컴파일러에서는 내장 함수 __builtin_popcount()를 사용하여 정수의 1비트 개수를 한 번에 구할 수 있습니다. 이를 활용하면 위 코드를 다음과 같이 훨씬 간결하게 작성할 수 있습니다.

int isEvilNumber(int n) {
    // 1의 개수가 짝수면 true(이블 넘버)
    return (__builtin_popcount(n) % 2 == 0);
}

이처럼 이블 넘버 판별은 2진수 변환 후 1의 개수만 세면 되므로, 시간 복잡도는 O(log N)으로 매우 효율적입니다. 숫자를 2로 나누면서 나머지를 확인하는 방식은 곧 비트를 하나씩 오른쪽으로 이동시키며 검사하는 것과 동일한 원리입니다.