【C++】xとのXORがxより大きくなる「x未満の値」の個数を数える方法

整数 x が与えられたとき、x 未満の数 y のうち「y と x の XOR（排他的論理和）を計算すると、結果が x より大きくなる」ような値の個数を数える問題を考えてみましょう。すべての組み合わせを順に調べる必要があるように見えますが、x を2進数で捉えることで少ない計算量で答えを求められる、ビット演算ならではの性質を利用した問題です。

XOR演算の真理値表

入力例と出力例

例1：x = 11 の場合

入力：int x = 11
出力：条件を満たす値の個数は 4

1〜10 の各数と x との XOR を計算すると、1 XOR 11 = 10（11未満・不成立）、2 XOR 11 = 9（不成立）、3 XOR 11 = 8（不成立）、4 XOR 11 = 15（成立）、5 XOR 11 = 14（成立）、6 XOR 11 = 13（成立）、7 XOR 11 = 12（成立）、8 XOR 11 = 3（不成立）、9 XOR 11 = 2（不成立）、10 XOR 11 = 1（不成立）となります。よって条件を満たすのは 4・5・6・7 の4個です。

例2：x = 12 の場合

入力：int x = 12
出力：条件を満たす値の個数は 3

同じく 1〜11 の各数と計算すると、1 XOR 12 = 13（成立）、2 XOR 12 = 14（成立）、3 XOR 12 = 15（成立）であり、4 以降の数との XOR はいずれも 12 未満になるため不成立です。よって条件を満たすのは 1・2・3 の3個です。

アルゴリズムの考え方

この問題の鍵は、「y < x かつ (x XOR y) > x」を満たす y の個数が、x の2進表現において 0 になっているビットの位置に対応する2の累乗の総和と一致するという性質です。たとえば x = 20（2進数で 10100）なら、0 のビットは下位から 1桁目・2桁目・4桁目に当たり、1 + 2 + 8 = 11 が答えとなります。手順は以下の通りです。

• 整数を入力として受け取り、変数 x に格納する。
• その値を処理用の関数に渡す。
• 結果を保持する変数 count を 0、桁の重みを表す変数 num を 1 で初期化する。
• x != 0 の間 WHILE ループを継続する。
• ループ内で x % 2 == 0（最下位ビットが 0）なら、count に num を加算する。
• num を2倍、x を2で割って、上位ビットへ処理を進める。
• ループを抜けたら count を返す。
• main 関数で結果を出力する。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

int XOR_smaller(int x){
    int count = 0;
    int num = 1;
    while (x != 0){
        if (x % 2 == 0){
            count = count + num;
        }
        num = num * 2;
        x = x / 2;
    }
    return count;
}

int main(){
    int x = 20;
    cout << "xより小さい値のうち、xとのXORがxより大きくなるものの個数: " << XOR_smaller(x);
    return 0;
}

実行結果

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

xより小さい値のうち、xとのXORがxより大きくなるものの個数: 11