位运算-lowbit

lowbit概念

  任意一个整数可被表达成二进制如: (6)₁₀ =(110)₂
  那么定义一个函数f=lowbit(x)，表示这个数的二进制表示中最低位的1所对应的值，lowbit(6)=2
  所以所以假设一个数的二进制最低位的1在从右往左数的第k位，那么它的lowbit值就是:2^k-1

lowbit 实现方式

1. x&(x^(x-1))
2. x&-x

解释:
  我们得到lowbit的值，只需要得到最后一个1的位置，并且把除了这个位置之外的所有位置全部置成零。然后输出就可以。
  看看x&(x^(x-1)),拿6来举例:
<center> (6)₁₀ -1=(101)₂ </center>
  对一个二进制数进行减1，那么会出现从这个这个数的最后一个1开始到最后的所有数都取反，即构成一个01111⋯的串。
  把这个数与原数异或，就会造成：第一个1以后的数（包括第一个1）全部取1.其他的位全部取0.即构成一个由一堆0后面跟一堆1的串。
  那么再把原式做一个与运算，那么除了原来的那个1（对应位都是1）为1，其他位全是0，完成任务。

  然后x&-x
根据补码性质,可以理解跟上边原理是一样的。