The text I was reading says that:
x & (x + (1 << n)) = x, with the run of set bits (possibly length 0) starting at bit n cleared.
I tried putting different values in the python console and saw that:
>>> 5 & (5 + (1 << 2))
1
However, when I tried putting in other different values instead of 2, I got 5 as the answer. I tried putting in values from 1 to 7.
I tried deriving the expression but I couldn't.
What must be a reasonable explanation for the same? And how does it work?
I tried putting in values from 1 to 7 [for n]
n = 0 is also fine. Actually let's look at that case first. So x & (x + 1).
If x is odd, then x is of the form a01k (some bit-string a, followed by a zero, followed by k ones). Adding 1 to it would carry through all the trailing ones and turn it into a10k. And-ing that with x cancels the old trailing ones with the new trailing zeroes, and that new 1 that appeared with the old 0. a stays the same. In other words: the trailing ones were reset.
If x is even, then adding 1 to it does not carry, the only effect is that the least significant bit becomes set. The AND with x then resets that bit again. Overall nothing happens.
If n is not zero, then it's as if the n least significant bits aren't there. The addition doesn't affect them, therefore the AND doesn't either. So in total, x & (x + (1 << n)) can be described as "if there is a run of ones starting at position n, zero out that run, otherwise do nothing".
A potentially interesting variant is x & (x + (x & -x)), which first uses x & -x to get a mask of the least significant set bit and then proceeds the same as the original expression. That would find the first run of ones and reset it.