C++で2進表現における0と1の個数のXORを求める方法

問題概要

この問題では、ひとつの整数が与えられます。求めるのは、その数を2進表現したときに含まれる「0」の個数と「1」の個数をそれぞれカウントし、2つの値のXOR（排他的論理和）を計算することです。

具体例を使って、問題の内容を確認してみましょう。

入力

n = 9

出力

0

説明

binary = 1001
0の個数 = 2
1の個数 = 2
2 ^ 2 = 0

9を2進数で表すと「1001」になり、「0」が2個、「1」が2個含まれています。そこで 2 XOR 2 = 0 という結果が得られます。

解決のためのアプローチ

この問題は、次の手順で解くことができます。

1. 与えられた数値を2進数として扱い、最下位ビットから順に各ビットを調べる
2. ビットが「0」なら0のカウントを、「1」なら1のカウントをそれぞれ増やす
3. すべてのビットを走査し終えたら、0の個数と1の個数のXORを返す

各ビットの判定には剰余演算（n % 2）を使用します。2で割った余りが0なら偶数（最下位ビットが0）、1なら奇数（最下位ビットが1）であるため、これを繰り返すことで全ビットを効率よく走査できます。

C++による実装例

上記の解法を実装したプログラムがこちらです。

サンプルコード

#include<iostream>
using namespace std;
int countXOR10(int n) {
    int count0s = 0, count1s = 0;
    while (n){
        (n % 2 == 0) ? count0s++ : count1s++;
        n /= 2;
    }
    return (count0s ^ count1s);
}
int main() {
    int n = 21;
    cout<<"XOR of count of 0s and 1s in binary of "<<n<<" is "<<countXOR10(n);
    return 0;
}

実行結果

XOR of count of 0s and 1s in binary of 21 is 1

コードの解説

この例では n = 21 を入力としています。21を2進数で表すと「10101」であり、「0」が2個、「1」が3個含まれます。したがって 2 XOR 3 = 1 となり、出力は「1」になります。

while ループの中では、三項演算子を使って現在の最下位ビットが0か1かを判定しています。n /= 2 によって数値を右に1ビットシフトするのと同じ効果が得られ、次のビットへ処理を進めます。ループは n が0になるまで続きます。

計算量は、2進表現の桁数（ビット数）に比例するため、時間計算量は O(log n)、補助的な変数のみで済むため空間計算量は O(1) となります。非常に効率的なアルゴリズムです。