Low Bits

x & (-x): 找到最后一位set bit以及follow的0

为什么?

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