lowbit(x)函数返回x二进制下最低位的1代表的十进制数,比如(二进制) x=1100 ,lowbit(x)代表 100
原理解析
lowbit(x)= x & (~x+1) 假设 x的二进制表示为 11100 ,那么 ~x 表示为 00011 ,~x+1=00100 , 最低位的1的 位数不变, 进行 & 运算 返回 100 证明: 假设最低位的1在第 k 位,后面还有 m 个0(m>=0),即..100(m个0) 那么取反运算后,后m位 0 都会变成 1 ,第k位变成 0 ,即...011(m个1) 再加上1 ,变成 ..100(m个0),而比k位高的几位 会取反 1&0=0 所以,最终结果返回 最低位 1 的十进制数 lowbit(x)= x & -x &运算 是对补码进行操作 x的补码是其原码 -x的补码是其符号位变成1,然后其余位 按位取反加 1,除了符号位变了 其余和(~x+1)一样,而符号位 1&0=0;
int lowbit(x){ return x&-x; }
int lowbit(x){ return x&(~x+1); }