Incrementing 'masked' bitsets

I'm currently in the process of writing a tree enumerator where I've come across the following problem:

I'm looking at masked bitsets, i.e. bitsets where the set bits are a subset of a mask, i.e. 0000101 with mask 1010101. What I want to accomplish is increment the bitset, but only with respect to the masked bits. In this example, the result would be 0010000. To make it a bit clearer, extract only the masked bits, i.e. 0011, increment them to 0100 and distribute them to the mask bits again, giving 0010000.

Does anybody see an efficient way to do this, short of implementing the operation by hand using a combination of bitscans and prefix masks?

3921 次浏览

小开

最佳答案

Just fill the non mask bits with ones so that they propagate carry:

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;

小开

While not intuitive compared to the accepted answer, this works in only 3 steps:

x = -(x ^ mask) & mask;

This can be verified as suggested by zch:

  -(x ^ mask)
= ~(x ^ mask) + 1  // assuming 2's complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1  // since x and ~mask have disjoint set bits

Then it becomes equivalent to the accepted answer.

小开

If the order of iteration is not that important, and a decrement operation will satisfy your needs, it is possible to use only two operations:

Let's start with

x = mask

and get previous value with

x = (x - 1) & mask

x - 1 part changes the last non-zero bit to zero, and sets all less significant bits to 1's. Then & mask part leaves only mask bits among them.