lowbit概念
任意一个整数可被表达成二进制如: (6)10 =(110)2
那么定义一个函数f=lowbit(x)，表示这个数的二进制表示中最低位的1所对应的值，lowbit(6)=2
所以所以假设一个数的二进制最低位的1在从右往左数的第k位，那么它的lowbit值就是:2k-1
lowbit 实现方式
- x&(x^(x-1))
- x&-x
解释:
我们得到lowbit的值，只需要得到最后一个1的位置，并且把除了这个位置之外的所有位置全部置成零。然后输出就可以。
看看x&(x^(x-1)),拿6来举例:
<center> (6)10 -1=(101)2 </center>
对一个二进制数进行减1，那么会出现从这个这个数的最后一个1开始到最后的所有数都取反，即构成一个01111⋯的串。
把这个数与原数异或，就会造成：第一个1以后的数（包括第一个1）全部取1.其他的位全部取0.即构成一个由一堆0后面跟一堆1的串。
那么再把原式做一个与运算，那么除了原来的那个1（对应位都是1）为1，其他位全是0，完成任务。
然后x&-x
根据补码性质,可以理解跟上边原理是一样的。
网友评论