CODEWITHSUNDEEP
algorithmbit-manipulation
lz96
lz96

Reputation: 2998

algorithm: How to generate numbers sorted by the number of 1 in its binary representation?

I am finding an operator to generate all numbers below 2^n in the order of the number of 1 in its binary representation. For example:

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

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

should give out something like:

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

(the order of numbers with the same number of 1 doesn't matter)

Is it possible to write a pure next() function without remembering any state?

This may looks like a duplicate of Encoding system sorted by the number of 1, but this question is asking about how to generate the next number instead of returning by index

Upvotes: 1

Views: 338

Answers (1)

lz96
lz96

Reputation: 2998

Finally I found the answer from here and n-m's comment.

The basic idea is to consider the number as a permutation of 0 and 1s. If cur is not the largest number with the same number of 1s, we can simply use next permutation algorithm to get the next one (with the implementation of bit tricks), otherwise we can return (1 << (number_of_1(cur) + 1)) - 1.

Here is an simple implementation. I guess it is possible to completely eliminate conditional jumps and iterations with some bit magic:

// 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 provides another solution:

// 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));
}

According to my micro-benchmark with 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

Upvotes: 1

Related Questions