算法:如何生成按二进制表示中 1 的个数排序的数字？

Question

我正在寻找一个运算符，以其二进制表示形式按照 1 的数量顺序生成 2^n 以下的所有数字。例如:

int next(int cur, int max) { /* ??? */ }

for (int i=0; i< 1<<6; i = next(i, 1<<6)) printf("%d ", i);

应该给出类似的东西:

0  1  2  4  8  16  32  3  5  6  9  10  12  17  18  20  24  33  34  36  40  48  7  11  13  14  19  21  22  25  26  28  35  37  38  41  42  44  49  50  52  56  15  23  27  29  30  39  43  45  46  51  53  54  57  58  60  31  47  55  59  61  62  63

(1相同的数字顺序无所谓)

是否可以在不记住任何状态的情况下编写纯 next() 函数？

---

这看起来像是 Encoding system sorted by the number of 1 的副本, 但是这个问题问的是如何生成下一个数字而不是通过索引返回

Answer 1

最后我从here找到了答案和 n-m's comment .

基本思想是将数字视为 0 的排列和 1秒。如果cur不是与1相同数量的最大数字s，我们可以简单地使用下一个排列算法得到下一个(通过位技巧的实现)，否则我们可以返回(1 << (number_of_1(cur) + 1)) - 1 .

这是一个简单的实现。我想用一些魔法完全消除条件跳转和迭代是可能的:

// https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
static int next_perm(unsigned int v)
{
    unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
    // Next set to 1 the most significant bit to change, 
    // set to 0 the least significant ones, and add the necessary 1 bits.
    return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));  
}

static int next(unsigned int cur, unsigned int max) {
    if (cur + 1 == max) return max;
    if (((cur - 1) | cur) >= max - 1) return (1 << (__builtin_popcount(cur) + 1)) - 1;
    return next_perm(cur);
}

int main() {
    for (volatile int i=0; i< 1<< 30; i = next(i, 1<<30));
}

The link given by @rici提供另一种解决方案:

// end with zero
template<typename UnsignedInteger>
UnsignedInteger next_combination(UnsignedInteger comb, UnsignedInteger mask) {
  UnsignedInteger last_one = comb & -comb;
  UnsignedInteger last_zero = (comb + last_one) &~ comb & mask;
  if (last_zero) return comb + last_one + (last_zero / (last_one * 2)) - 1;
  else if (last_one > 1) return mask / (last_one / 2);
  else return ~comb & 1;
}

int main() {
    for (volatile int i = 1; i; i = next_combination(i, (1 << 30) -1));
}

根据我使用 gcc-8.1.1 的微基准测试 -O3 -flto :

➜  bitmagic git:(master) ✗ time ./next-1
./next-1  4.27s user 0.01s system 99% cpu 4.313 total
➜  bitmagic git:(master) ✗ time ./next-2
./next-2  12.42s user 0.00s system 99% cpu 12.436 total