The steps I took to derive the answer here
For numbers in binary format, incrementing by 1 is same as inverting the rightmost 0 and all the 1’s following the 0.
For example:
x : 00000101
^^ // invert these two bits
x + 1 : 00000110
In this case with masks, first we need to locate the rightmost 0 belonging to mask, and then secondly, invert the located 0 and the following 1’s belonging to mask.
mask : 01010101
x : 00010001
^ ^ // these two bits needs to be reversed
The first step of locating the rightmost 0 can be done by finding the rightmost 1 of x ^ mask.
x : 00010001
^ // rightmost 0 belonging to mask
mask : 01010101
x ^ mask (= y) : 01000100
^ // we need to locate this 1
Finding the rightmost 1 of y can be done by y & -y. (This unary minus hack is from a book called Hacker’s Delight)
y : 01000100
-y : 10111100
y & -y (= z) : 00000100
^ // found!
We’ve now located the rightmost 0 of x belonging to mask. The reversal of this 0 can be done by bit-wise OR with z.
Next we need to reverse the 1’s of x on the right side of the above location. This can be done by x & -y.
x : 00010001
-y : 10111100
x & -y (= w) : 00010000
^ // bit cleared
In this step, other 1’s that needs to be preserved doesn’t become 0. I think this can be proved by the fact that the 1’s of x on the left of rightmost 0 (belonging to mask) become 0 in y (because the bit is XORed with mask) and it always will be 1 in -y.
x : 00010001
^ // this 1 needs to be preserved
y : 01000100
^ // it becomes 0 in y
-y : 10111100
^ // and it always will be 1 on -y
Then, combining z and w with bit-wise OR gives the answer.
z : 00000100 w : 00010000 z | w : 00010100
To sum up, this results in 5 steps as follows.
y = x ^ mask; minus_y = -y; z = y & minus_y; w = x & minus_y; x + 1 = z | w;
But since z | w = (y & -y) | (x & -y) = (y | x) & -y = mask & -y by boolean logic, this can be reduced to 3 steps:
x + 1 = mask & -(x ^ mask)
Pensieve 