note: I rewrote this post because of its popularity.
In this post I will assume that the reader knows the bitwise operators and what they do (if not, see Low Level Bit Hacks You Absolutely Must Know), to avoid having to cover the basics.
The rightmost bit (not to be confused with the least-significant bit), also called "rightmost 1", is the lowest bit that is set (rightmost zero is the lowest bit that is not set). So zero, unlike all other numbers, doesn't have a rightmost bit. The rightmost bit is interesting because surprisingly many useful operations can be done on it.
Here's a small selection of potentially useful basic "rightmost bit/zero operations":
x - 1 | Remove the rightmost bit and smear it to the right. (zero is interpreted as having a rightmost bit just beyond the msb) |
x & (x - 1) | Remove the rightmost bit. |
x & -x | Isolate the rightmost bit. |
x | (x + 1) | Set the rightmost zero. |
x | ~(x + 1) | Isolate the rightmost zero (as an inverted mask). |
How it works
Manipulation of the rightmost bit makes use of the properties of the carry/borrow process, namely that it propagates from the lsb to the msb, changes the bits it touches, and can be stopped. For example, the simplest operation operation, x - 1 just runs a borrow through the zeroes on the right, changing all of them to ones, the borrow is stopped by the rightmost one (which is changed to a zero). Effectively it inverted the part of the number that includes the rightmost bit and spans to the right, and left the rest alone. ANDing that number with x (as in the "remove the rightmost bit" operation) then sets that rightmost part to all zeroes (because x & ~x = 0) and leaves the rest of the number alone (because x & x = x).
Since -x = ~(x - 1), clearly negation is a kind of "opposite" of subtracting 1; the rightmost part (including the rightmost 1) is not change, and the leftmost part is changed. So x & -x also gives the opposite thing of x & (x - 1), namely just the rightmost bit (instead of everything else).
The other two operations from the table can be derived by taking ~operation(~x) and simplifying it:
~(~x & (~x - 1)) = // use the definition of subtraction: a - b = ~(~a + b) ~(~x & ~(x + 1)) = // use De Morgan's law x | (x + 1)
~(~x & -~x) = // use the definition of negation: -a = ~(a - 1) ~(~x & ~(~x - 1)) = // use De Morgan's law x | (~x - 1) = // use the definition of subtraction: a - b = ~(~a + b) x | ~(x + 1)
Using the same principles, more complicated operations can be constructed. For example (by chaining two operations on the rightmost bit), by first smearing the rightmost 1 to the right, the rightmost run of ones is now in a good position to get rid of it (by adding one and ANDing):
(x | (x - 1)) + 1 & x
The same can also be accomplished differently (no better, just different), by instead of smearing the rightmost bit to the right so that it can be affected by the +1, adding a big enough number - that number is, of course, the isolated rightmost bit, so we get this:
x + (x & -x) & x
A good overview of the basic rightmost-bit operations can be found here.
Next time, why rightmost bits are relevant in testing divisibility by even numbers.