我想有效地(通过使用bit hacks(生成给定数字k的所有整数，这样它们就具有均匀的汉明权重，而无需明确计算它们的汉明权重。对我来说，这是按升序还是降序完成并不重要。
一个好处(相关任务(是，如果我能生成所有具有均匀汉明权重的整数，这些整数是 k 的子集(在格雷码意义上(。
例： 输入> k=14(二进制 1110(
输出全> 3 (0011(， 5(0101(， 6 (0110(， 9 (1001(， 10 (1010(， 12 (1100(
输出子集 -> 6 (0110(， 10 (1010(， 12 (1100(
使用弹出计数的示例代码：
for (unsigned int sub=1; sub<k; sub++){
if (__builtin_popcount(sub) % 2 == 0){
cout << sub << endl;
}
}
使用子集的弹出计数的示例代码：
for (unsigned int sub=((k-1)&k); sub!=0; sub=((sub-1)&k)){
if (__builtin_popcount(sub) % 2 == 0){
cout << sub << endl;
}
}
我们可以在节点中构建一个带有数字的树，每个节点有两个子节点，一个具有翻转位号x，另一个具有未翻转位号x。我们需要排除所有值大于初始值的子项。我们可以将 popcount 存储在一个变量中，并在每次翻转位时根据翻转位值递减和递增，从而避免每次更改变量时计算 popcount。
我不知道这种方法是否更快。我想它可能更快，但递归函数的开销可能太大。 这很有趣：
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cinttypes>
#include <cassert>
#include <bitset>
#include <cstring>
namespace gen {
bool isEven(unsigned int x) {
return x % 2 == 0;
}
// find last set bit, just like ffs, but backwards
unsigned int fls(unsigned int x)
{
assert(x >= 1);
if (x == 0) {
return 0;
}
#ifdef __GNUC__
const unsigned int clz = __builtin_clz(x);
#else
#error find clz function in C++
#endif
assert(clz >= 1 && (sizeof(x) * CHAR_BIT) >= clz + 1);
return (sizeof(x) * CHAR_BIT) - clz - 1;
}
unsigned int popcount(unsigned int x) {
#ifdef __GNUC__
return __builtin_popcount(x);
#else
return std::bitset<sizeof(x)*CHAR_BIT>(x).count();
#endif
}
/**
* Generates all integers up a given number k with even hamming weight
* @param out - output vector with push_backed results
* @param greycodesubset - set to true, if only interested in grey subset integers only
* @param startk - starting k value
* @param k - the current number value
* @param pos - one plus the position of the bit in number k that we will change in this run
* @param popcount - Hamming weight of number k up to position pos
* @param changes - the number of bits changed in number k since startk. Used only if greycodesubset = true
*/
void loop(std::vector<unsigned int>& out, const bool& greycodesubset,
const unsigned int& startk,
unsigned int k, unsigned int pos, unsigned int popcount,
unsigned int changes)
{
// k > startk may happen for example for 0b10, if we flip last byte, then k = 0b11
if (startk < k) {
return;
}
// end of recusive function
if (pos == 0) {
if (isEven(popcount) && k != 0) {
out.push_back(k);
}
return;
}
// decrement pos
--pos;
const int mask = 1 << pos;
const bool is_pos_bit_set = k & mask;
// call without changes
loop(out, greycodesubset, startk,
k, pos, popcount + (is_pos_bit_set ? +1 : 0), changes);
// when finding grey code subset only we can change maximum 1 byte
if (greycodesubset) {
if (changes >= 1) {
return;
}
++changes;
}
// call with toggled bit number pos
loop(out, greycodesubset, startk,
k ^ mask, pos, popcount + (!is_pos_bit_set ? +1 : 0), changes);
}
std::vector<unsigned int> run(const unsigned int& k, const bool& greycodesubsetonly)
{
assert(k > 0);
std::vector<unsigned int> out;
if (k < 2) return out;
loop(out, greycodesubsetonly, k, k, fls(k) + 1, 0, 0);
return out;
}
} // namespace gen
int main()
{
const unsigned int k = 14;
const int bits_in_k = 4;
std::vector<unsigned int> out = gen::run(k, false);
std::vector<unsigned int> out_subset = gen::run(k, true);
std::cout << "input-> k=" << k << "(" << std::bitset<bits_in_k>(k).to_string() << ") " << std::endl;
std::cout << "output all-> ";
std::for_each(out.begin(), out.end(), [](int v) {
std::cout << v << "(" << std::bitset<bits_in_k>(v).to_string() << ") ";
});
std::cout << std::endl;
std::cout << "output subsets-> ";
std::for_each(out_subset.begin(), out_subset.end(), [](int v) {
std::cout << v << "(" << std::bitset<bits_in_k>(v).to_string() << ") ";
});
std::cout << std::endl;
return 0;
}
input-> k=14(1110)
output all-> 12(1100) 10(1010) 9(1001) 6(0110) 5(0101) 3(0011)
output subsets-> 12(1100) 10(1010) 6(0110)