在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