C++でイビルナンバー（悪数）とオディアスナンバーを判定する方法

イビルナンバーとオディアスナンバーとは？

この問題では、整数 N が与えられ、その数がイビルナンバー（Evil Number）かオディアスナンバー（Odious Number）かを判定します。

イビルナンバー：2進表現における「1」の個数が偶数である正の整数のことです。

例：5、17

オディアスナンバー：2進表現における「1」の個数が奇数である正の整数のことです。

例：4、6

具体例で問題を理解しよう

入力：N = 65

出力：イビルナンバー

解説：

65 の2進表現は 1000001 です。「1」が2つ含まれており、その個数は偶数なので、65 はイビルナンバーであると判定できます。

解法のアプローチ

シンプルな解き方は次の通りです。

1. 対象となる数の2進表現を求める。
2. 2進表現の中に含まれる「1」の個数を数える。
3. 個数が偶数であればイビルナンバー、奇数であればオディアスナンバーと判定する。

なお、C++ では除算と剰余演算を使って下位ビットから順に調べる方法が基本ですが、GCC や Clang では組み込み関数 __builtin_popcount(n) を使うことで、「1」の個数を1行で取得することも可能です。

解法の動作を示すプログラム

サンプルコード

#include <iostream>
using namespace std;

int isEvilNumber(int n) {

    int count = 0;
    while (n != 0) {
        int r = n % 2;
        if(r == 1)
            count++;
        n = n / 2;
    }
    
    if (count % 2 == 0)
        return 1;
    else
        return 0;
}

int main(void)
{
    int num = 2049;
    if (isEvilNumber(num) )
        cout<<"The number "<<num<<" is an Evil Number";
    else
        cout<<"The number "<<num<<" is an Odious Number";
    return 0;
}

出力結果

The number 2049 is an Evil Number

プログラムのポイント

このコードでは、isEvilNumber() 関数内で while ループを使い、数値を2で割りながら余りを確認しています。余りが1であればカウントを増やし、最終的にカウントが偶数かどうかで判定を行います。

2049 の2進表現は 100000000001 であり、「1」が2つ（偶数個）含まれるため、イビルナンバーとして出力されます。