c++ - 生成具有偶数汉明权重的整数(popcount)c++

Question

我想有效地(通过使用 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)

使用 popcount 的示例代码:

for (unsigned int sub=1; sub<k; sub++){
  if (__builtin_popcount(sub) % 2 == 0){
    cout << sub << endl;
  }
}

使用子集 popcount 的示例代码:

for (unsigned int sub=((k-1)&k); sub!=0; sub=((sub-1)&k)){
  if (__builtin_popcount(sub) % 2 == 0){
    cout << sub << endl;
  }
}

Answer 1

我们可以用节点中的数字构建一棵树，每个节点有两个 child ，一个翻转的位数为 x，另一个没有翻转的位数为 x。我们需要排除所有值大于初始值的 child 。我们可以将 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)