fast way to shift bits to positions given in a mask

Question

I am searching for a fast way of iterating over all possible assignments of bits set in a mask.

Example:

mask = 0b10011

result = {0b00000, 0b00001, 0b00010, 0b00011, 0b10000, 0b10001, 0b10010, 0b10011}

I need to iterate over all of them.

Currently I use a similar code to this one, which works well:

int count = popCount(mask);
uint64_t number = 0;
for(uint64_t number = 0; number < (1 << count); ++number)
{
    uint64_t result = shiftBits(mask, number, count);
    //work with result
    //only some light operations
}
// shiftBits(0b10011, 0b101, 3) == 0b10001
// shiftBits(0b10011, 0b111, 3) == 0b10011
// shiftBits(0b10011, 0b000, 3) == 0b00000
uint64_t shiftBits(uint64_t mask, uint64_t number, int count) {
    uint64_t result = 0;
    for(int i = 0; i < count; ++i)
    { 
        uint64_t least = (mask & ~(mask - 1)); // get uint64_t with only least significant 1 set
        uint64_t bitSet = number & uint64_t(1); // check if last bit in number is set
        result |= least * bitSet; // if last bit is set, then set corresponding position in result
        mask &= mask - 1; // clear lsb set in mask
        number = number >> 1; // make 2nd lsb the next one to check
    }
    return result;
}

Example for shiftBits:

mask =   0b10011001
number = 0b1  01  0 = 0b1010
result = 0b10001000

But I wonder if anyone knows a faster way of performing the operation done in shiftBits, or if there is a faster way of creating this assignments. Maybe some bitmagic or a way that has no "read after write" and "write after read" conflicts?

Answer 1

Updated version, replacing the ascending enumeration with an easier expression:

uint64_t i = 0;
do {
    // use i
    i = (i - mask) & mask;
} while (i);

This really does the same thing as the old answer, but saves an operation. You could view this as subtracting -1 rather than adding 1, but it's a masked -1.

---

No shifting necessary: you can do a masked increment. The idea there is to make carry go through the zeroes of the mask by temporarily setting them to 1, and then removing them afterwards. For example:

uint64_t i = 0;
do {
    // use i
    i = ((i | ~mask) + 1) & mask;
} while (i);

It's slightly simpler to iterate backwards, because a decrement borrows through zeroes, and the masked-out bits are already zero, for example:

uint64_t i = 0;
do {
    i = (i - 1) & mask;
    // use i
} while (i);