- A+

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?

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); `