c++ - 权重增加的枚举位集。(C++ & Boost::dynamic_bitset)

Question

如何在 C++ 中实现算法？这样的任务，有一个bitset大小N。需要一直遍历所有的bitset overhang k = 1,2, ... l，直到序列的总数不等于M。也就是说，结果应该是数组：

0 ... 001
0 ... 010
0 ... 100
...
1 ... 000
0 ... 011
0 ... 101
0 ... 110
....
....
etc

权重为 1 时，向左清除按位移位。但是如何处理权重 k = 2,3, ... 同时保持算法的质量的位集我不知道。请帮忙，有人可以面临类似的挑战。使用 boost :: dynamic_bitset 实现的位集。C++ 语言。

score 1 · Accepted Answer

您可能会发现此 C 代码很有帮助。

函数 make_sets 生成具有一定权重的所有位模式，因此 main 多次调用它以首先生成具有 1 个设置位的模式，然后是 2 个设置位等。

#include <stdio.h>

#define BYTETOBINARYPATTERN "%d%d%d%d%d"
#define BYTETOBINARY(byte)  \
  (byte & 0x10 ? 1 : 0), \
  (byte & 0x08 ? 1 : 0), \
  (byte & 0x04 ? 1 : 0), \
  (byte & 0x02 ? 1 : 0), \
  (byte & 0x01 ? 1 : 0) 

/* Make all bitsets with bits_to_add set bits in the least significant num_bits bits 
The most significant bit are taken from high_bits.*/
void make_sets(int high_bits, int bits_to_add, int num_bits) {
    // Recurse on the position of the next set bit
    int i;
    if (bits_to_add) {
        for(i=bits_to_add-1;i<num_bits;i++)
            make_sets(high_bits + (1<<i), bits_to_add-1, i);
    } else {
        printf (BYTETOBINARYPATTERN"\n", BYTETOBINARY(high_bits));
    }
}

int main(int argc,char *argv[]) {
    int M;
    for(M=1;M<=5;M++)
        make_sets(0,M,5);
}

这将产生输出：

c++ - 权重增加的枚举位集。(C++ & Boost::dynamic_bitset)

1 回答 1

Related

Reference