C++でビットごとのORがKに等しくなるN個の異なる整数を見つける方法

概要

2つの整数 N と K が与えられたとき、N 個の相異なる整数を選んでビットごとのOR（論理和）を計算した結果が、ちょうど K に等しくなるような組み合わせを見つけるのがこの問題の目的です。条件を満たす解が存在しない場合は -1 を出力します。

入力例と出力例

例1：解が存在する場合

入力：

N = 4, K = 6

出力：

6 0 1 2

例2：解が存在しない場合

入力：

N = 11, K = 6

出力：

-1

この場合、条件を満たす組み合わせが存在しないため、解を求めることはできません。

解法のアプローチ

• 複数の数のビットごとのORが K になるとき、K で 0 になっているビット位置は、すべての数においても必ず 0 でなければなりません。

• そのため、値を自由に設定できるのは K で 1 になっているビット位置だけです。このビットの個数を Bit_K と呼びます。

• Bit_K 個の自由なビットから作れる相異なる数は最大で pow(2, Bit_K) 個です。1つ目の数として K そのものを採用すれば、残りの N − 1 個の数は「K で 0 のビット位置をすべて 0 に設定し、K で 1 のビット位置には K 以外の任意のビットの組み合わせを割り当てる」ことで構成できます。

• もし pow(2, Bit_K) < N であれば、N 個の相異なる整数を作ることは不可能であり、答えは -1 になります。

C++での実装例

// アプローチのC++実装
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX1 32
ll pow2[MAX1];
bool visited1[MAX1];
vector<int> ans1;
// MAX1 までの2のべき乗を
// すべて事前計算する関数
void power_2(){
   ll ans1 = 1;
   for (int i = 0; i < MAX1; i++) {
      pow2[i] = ans1;
      ans1 *= 2;
   }
}
// x のセットビットの数を返す関数
int countSetBits(ll x1){
   // セットビットの数を格納する変数
   int setBits1 = 0;
   while (x1 != 0) {
      x1 = x1 & (x1 - 1);
      setBits1++;
   }
   return setBits1;
}
// K で 0 になっているビット位置を
// すべて 0 に保ちながら num を答えに追加する関数
void add(ll num1){
   int point1 = 0;
   ll value1 = 0;
   for (ll i = 0; i < MAX1; i++) {
      // ビット i は K で 0
      if (visited1[i])
         continue;
      else {
         if (num1 & 1) {
            value1 += (1 << i);
         }
         num1 /= 2;
      }
   }
   ans1.push_back(value1);
}
// ビットごとのORが K になる N 個の
// 相異なる数を見つけて出力する関数
void solve(ll n1, ll k1){
   // K 自身を1つの数として選ぶ
   ans1.push_back(k1);
   // K のセットビットの数を求める
   int countk1 = countSetBits(k1);
   // N 個の相異なる整数を得ることは不可能
   if (pow2[countk1] < n1) {
      cout << -1;
      return;
   }
   int count1 = 0;
   for (ll i = 0; i < pow2[countk1] - 1; i++) {
      // K で 0 のビットをすべて 0 にしてから
      // i を答えに追加する
      add(i);
      count1++;
      // N 個の相異なる数が生成できたら終了
      if (count1 == n1)
         break;
   }
   // 生成した数を出力する
   for (int i = 0; i < n1; i++) {
      cout << ans1[i] << " ";
   }
}
// ドライバーコード
int main(){
   ll n1 = 4, k1 = 6;
   // 2のべき乗をすべて事前計算
   power_2();
   solve(n1, k1);
   return 0;
}

コードのポイント

• power_2()：2のべき乗をあらかじめ配列に計算しておくことで、以降の判定を高速化しています。
• countSetBits()：x & (x - 1) を繰り返す古典的なビット演算のテクニックで、セットビット（1 になっているビット）の数を効率よく数えます。
• add()：K で 0 のビット位置をすべて 0 に保ちながら、与えられた数値を再構成して答えのリストに追加します。
• solve()：まず K 自身を答えの先頭に加え、K のセットビット数から作れる総数が N 未満であれば -1 を出力します。十分な数が作れる場合は、0 から順に数値を変換しながら、N 個そろうまで生成を続けます。

各数値の生成には最大32回程度のループしか必要ないため、全体の計算量は O(N × 32) となり、非常に効率的なアルゴリズムです。

出力

6 0 1 2