在C ++中找到按位或等于K的N个不同的数字

概念

对于给定的两个整数N和K，我们的任务是确定N个不同的整数，它们的按位OR等于K。已经发现，如果不存在任何可能的答案，则打印-1。

输入项

N = 4, K = 6

输出结果

6 0 1 2

输入项

N = 11, K = 6

输出结果

-1

找不到任何解决方案。

方法

• 我们知道，如果一个数字序列的按位“或”为K，则所有K中为0的所有位索引也必须为零。

• 结果，我们只有那些位置可以更改，其中K中的bit为1。让该计数为Bit_K。

• 目前，我们可以使用Bit_K位创建pow(2,Bit_K)不同的数字。结果，如果我们将一个数字本身视为K，则可以通过将每个数字中所有在K中为0的所有位设置为0以及对其他位位置对Bit_K进行任意排列，来构造剩余的N – 1数字K以外的其他位。

• 已经看到，如果pow(2,Bit_K)<N，则我们无法确定任何可能的答案。

示例

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX1 32
ll pow2[MAX1];
bool visited1[MAX1];
vector<int> ans1;
//显示函数进行预计算
//所有2的幂直到MAX-
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;
}
//显示将num添加到答案的功能
//通过将所有位位置设置为0-
//在K中也为0-
void add(ll num1){
   int point1 = 0;
   ll value1 = 0;
   for (ll i = 0; i < MAX1; i++) {
      //K中的位i为0-
      if (visited1[i])
         continue;
      else {
         if (num1 & 1) {
            value1 += (1 << i);
         }
         num1 /= 2;
      }
   }
   ans1.push_back(value1);
}
//显示查找和打印N个不同字符的功能
//按位或为K的数字
void solve(ll n1, ll k1){
   //选择K本身为一个数字
   ans1.push_back(k1);
   // Find the count设置位 in 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++) {
      //之后将我添加到答案中
      //将所有位设置为0-
      //在K中为0-
      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;
}

输出结果

6 0 1 2