# How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit?

In a code, I saw someone use:

n&(n-1) to get the least significant bit of n ⇒ 101000 will return 1000

n&(-n) to remove the lsb from n ⇒ 101000 will return 100000.

This sounds magical to me. Is there any proof for these?

Thanks a lot!

For $$n=0b101000$$ we have $$n-1=0b100111$$, so $$n \& (n-1)=0b100000$$.
As to the second, then knowing $$-n=\sim n+1$$ we have $$-n= 0b10111 +1 = 0b11000$$ so $$n \& (-n)= 0b101000 \& 0b11000= 0b1000$$.
1. Let's take $$n \in \mathbb{N}$$. Suppose $$k$$ is first one in its binary expansion i.e. $$n=2^m a_m+ \cdots + 2^k a_k$$, where $$m \geqslant k$$.Then $$n \& (-n) = 2^k$$ proof: as we know $$-n=\sim n+1$$. So, first step, $$\sim n$$, gives inversion for each bit. Hence in bits lower then $$k$$ we will have ones and in bit $$k$$ we will have zero. Now adding $$1$$ gives all zeros in bits lower then $$k$$ and in bit $$k$$ we again have one, but all upper bits are reversed. So $$-n$$ have in all bits more then $$k$$ reversed values with respect to $$n$$, which gives result.
2. Again let's take $$n \in \mathbb{N}$$. Suppose $$k$$ is first one in its binary expansion i.e. $$n=2^m a_m+ \cdots + 2^k a_k$$, where $$m \geqslant k$$. If we consider $$n-1$$, then we get zero in $$k$$-th bit. So $$n$$ and $$n-1$$ have different coefficient only for bit $$k$$. This gives, that in $$n \& (n-1)$$ we have all coefficients same as in $$n$$ besides $$k$$-th bit is zero.