Low Bits
x & (-x): 找到最后一位set bit以及follow的0
为什么?
-x = ~x + 1可以得到-x和x几乎是完全取反,但是这个+1带来了一定的重合。- 如果
x的某位是1, 那么~x的这一位就是0,且只有1&1 = 1 - 那我们可知取
x & -x的时候为能取到一位1时,仅当x的后缀为10...0。这样一来~x = 01...1而`-x =~x + 1 = 1…1 + 1 = 10…0 - 从上我们可以得知
x & -x可以得到x的后缀10...0 - 至于前面是否有重叠?因为
~x的0之前都与x取反,而+1影响不到0之前的位数,故0&1 = 0不会取到前面的值