fast way to shift bits to positions given in a mask

  • A+
Category:Languages

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

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: