C++でnとのXORがより大きな値になる小さい数の個数を数える方法

整数 num が与えられたとき、num より小さい数の中で、num との XOR(排他的論理和)を取った結果が num 自身の値よりも大きくなるものの個数を求めるのが、この記事のテーマです。

XOR演算の真理値表

XOR は、2つのビットが異なる場合に 1 を返し、同じ場合に 0 を返すビット単位の演算です。真理値表は以下の通りです。

入出力例

例1:num = 11 の場合

入力 − int num = 11

出力 − n とのXORがより大きな値になる小さい数の個数 − 4

説明 −

num が 11 ということは、11 未満の各数値と 11 との XOR を順に調べます。
1 XOR 11 = 10 < 11(偽)、2 XOR 11 = 9 < 11(偽)、3 XOR 11 = 8 < 11(偽)、4 XOR 11 = 15 > 11(真)、5 XOR 11 = 14 > 11(真)、6 XOR 11 = 13 > 11(真)、7 XOR 11 = 12 > 11(真)、8 XOR 11 = 3 < 11(偽)、9 XOR 11 = 2 < 11(偽)、10 XOR 11 = 1 < 11(偽)
条件を満たすのは 4・5・6・7 の4個です。

例2:num = 12 の場合

入力 − int num = 12

出力 − n とのXORがより大きな値になる小さい数の個数 − 3

説明 −

num が 12 の場合は、12 未満の各数値と 12 との XOR を調べます。
1 XOR 12 = 13 > 12(真)、2 XOR 12 = 14 > 12(真)、3 XOR 12 = 15 > 12(真)、4 XOR 12 = 8 < 12(偽)、5 XOR 12 = 9 < 12(偽)、6 XOR 12 = 10 < 12(偽)、7 XOR 12 = 11 < 12(偽)、8 XOR 12 = 4 < 12(偽)、9 XOR 12 = 5 < 12(偽)、10 XOR 12 = 6 < 12(偽)、11 XOR 12 = 7 < 12(偽)
条件を満たすのは 1・2・3 の3個です。

アルゴリズムの考え方

n を2進数で見たとき、n のビットが 0 になっている位置 p に注目するのがポイントです。最上位ビットがその位置 p であるような数 x は、n がそれより上位の桁に 1 を持っている限り、必ず n より小さくなります。さらに、x と n の XOR は位置 p で 1 になり(n は 0)、それより上位の桁では n と一致するため、結果は必ず n より大きくなります。位置 p を最上位ビットとする数は下位 p ビットの組み合わせだけ存在するので、答えは「n の 0 ビットの各位置 p に対する 2^p の総和」となります。

プログラムで使用する手順

• 整数を入力として受け取り、変数 num に格納します。
• num の値を処理用の関数に渡します。
• 結果を保持するための一時変数 count を用意します。
• num > 0 の間、WHILE ループを繰り返します。
• ループ内では、num & 1 の結果が 0(最下位ビットが0)であれば、count に pow(2, temp) を加算します。
• temp の値を1ずつ増やします。
• num を num >>= 1 として1ビット右シフトします。
• 最後に count を返します。
• 結果を出力します。

サンプルコード

#include <iostream>
#include <cmath>
using namespace std;

// n とのXORが n より大きくなる小さい数の個数を数える
int XOR_greater(int n){
    int temp = 0;
    int count = 0;
    while (n > 0){
        if ((n & 1) == 0){
            count += pow(2, temp);
        }
        temp++;
        n >>= 1;
    }
    return count;
}

int main(){
    int n = 20;
    cout << "n とのXORが n より大きくなる小さい数の個数: " << XOR_greater(n) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

n とのXORが n より大きくなる小さい数の個数: 11

このコードでは n = 20(2進数で 10100)を設定しています。0 になっているビットは下から 0 番目・1 番目・3 番目なので、2⁰ + 2¹ + 2³ = 1 + 2 + 8 = 11 が出力されます。計算量は O(log n)、追加メモリは O(1) で済むため、非常に効率的な解法です。