lowbit

定义：$lowbit(n)$定义非负整数$n$在二进制表示下“最后一个$1$及其后面所有的$0$”。

例如：$10=(1010)_2$，则$lowbit(10)=(10)_2=2$

原理： 假设$n$的第$k$位是$1$，第$0$ ~ $k-1$位都是$0$。

先把$n$取反，则变成第$k$位是$0$，第$0$ ~ $k-1$位都是$1$。

再$+1$，因为进位，后面的$1$都变成$0$，第$k$位变成$1$，前面不变。

与之前的$n$做与运算，就只剩下第$k$位是$1$了，即为$lowbit(n)$。

所以$lowbit(n)=n\&(\sim n+1)$。

又因为补码表示下$\sim n = -1-n$ ，所以$lowbit(n)=n\&-n$