How to reset the Nth set bit of a bit mask?-CodePudding

Given a bit mask (with M bits set, i.e. popcount(bit_mask) == M), I would like to generate M distinct bit masks that have 1 set bit (of the given bit mask) toggled.

The above problem is reduced to the current Title, "How to reset the Nth set bit of a bit mask"

For a bit mask 0xE7 (popcount(0xE7) == 6), the following 6 bit masks will be generated

0xE6 (the 1st set bit is toggled)
0xE5 (the 2nd set bit is toggled)
0xE3 (the 3rd set bit is toggled)
0xC7 (the 4th set bit is toggled)
0xA7 (the 5th set bit is toggled)
0x67 (the 6th set bit is toggled)

My current codes use parallel bit deposit instruction (of Intel processor), but it is not portable (I think).

_pdep_u32(~0x1U, 0xE7U) == 0xE6U
_pdep_u32(~0x2U, 0xE7U) == 0xE5U
_pdep_u32(~0x4U, 0xE7U) == 0xE3U
_pdep_u32(~0x8U, 0xE7U) == 0xC7U
_pdep_u32(~0x10U, 0xE7U) == 0xA7U
_pdep_u32(~0x20U, 0xE7U) == 0x67U

CodePudding user response：

Since you need to generate the whole sequence of masks, you can enumerate the 1 bits in order instead of providing random access.

That is easy to do with the standard bit operations.

To enumerate the 1 bits:

for (mask_bit = mask&-mask; mask_bit; mask_bit = mask&~(mask-(mask_bit<<1))) {

    // mask_bit is the next 1 bit in mask
    // next output mask is then mask &~ mask_bit
}