Bit hack to generate all integers with a given number of 1s

Question

I forgot a bit hack to generate all integers with a given number of 1s. Does anybody remember it (and probably can explain it also)?

Answer 1

To add onto @sehe's answer included below (originally from Dario Sneidermanis also at http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation.)

#include <utility>
#include <iostream>
#include <bitset>

using I = uint8_t;

auto dump(I v) { return std::bitset<sizeof(I) * __CHAR_BIT__>(v); }

I bit_twiddle_permute(I v) {
    I 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.
    I w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));  
    return w;
}

int main() {
    I p = 0b001001;
    std::cout << dump(p) << "\n";
    for (I n = bit_twiddle_permute(p); n>p; p = n, n = bit_twiddle_permute(p)) 
{
        std::cout << dump(n) << "\n";
    }
}

There are boundary issues with bit_twiddle_permute(I v). Whenever v is the last permutation, t is all 1's (e.g. 2^8 - 1), (~t & -~t) = 0, and w is the first permutation of bits with one fewer 1s than v, except when v = 000000000 in which case w = 01111111. In particular if you set p to 0; the loop in main will produce all permutations with seven 1's, and the following slight modification of the for loop, will cycle through all permutations with 0, 7, 6, ..., 1 bits set -

for (I n = bit_twiddle_permute(p); n>p; n = bit_twiddle_permute(n)) 

If this is the intention, it is perhaps worth a comment. If not it is trivial to fix, e.g.

if (t == (I)(-1)) { return v >> __builtin_ctz(v); }

So with an additional small simplification

I bit_twiddle_permute2(I v) {
    I t = (v | (v - 1)) + 1;
    if (t == 0) { return v >> __builtin_ctz(v); }
    I w = t | ((~t & v) >> (__builtin_ctz(v) + 1));
    return w;
}

int main() {
    I p = 0b1;
    cout <<  dump(p) << "\n";
    for (I n = bit_twiddle_permute2(p); n>p; n = bit_twiddle_permute2(n)) {
        cout << dump(n) << "\n";
    }
}

The following adaptation of Dario Sneidermanis's idea may be slightly easier to follow

I bit_twiddle_permute3(I v) {
    int n = __builtin_ctz(v);
    I s = v >> n;  
    I t = s + 1;  
    I w = (t << n) | ((~t & s) >> 1);
    return w;
}

or with a similar solution to the issue I mentioned at the beginning of this post

I bit_twiddle_permute3(I v) {
    int n = __builtin_ctz(v);
    I s = v >> n;  
    I t = s + 1;  
    if (v == 0 || t << n == 0) { return s; }
    I w = (t << n) | ((~t & s) >> 1);
    return w;
}