本文共 1580 字,大约阅读时间需要 5 分钟。
现在令 x = 10101000,接下来我们算一下 x&(x-1)的结果。
首先我们回忆一下二进制减法的规则:
0-0=1-1=0 1-0=1 0-1=1(向高位借位) 例如,(11000011)2-(00101101)2的算式如下: 11000011 被减数 00101101 减数 --1111 借位 (减号是对齐美观用的) ------------------- 10010110 差数
回到刚才的运算,根据二进制减法的规则,我们得:
x-1 = 10100111, & x = 10101000, x & (x-1) = 10100000我们可以看出,x的最右边的1变成了0,如果我们继续对得到的结果再次执行这样的运算时,发现结果又变为 10000000,由此我们得到结论:x&(x-1) 是将二进制数最右边的1变成0,如果没有1则生成的二进制位全为0。
???
我们看下面程序会输出什么 ???#includeint function(int num){ int count = 0; while(num) { count++; num = num&(num-1); } return count;}int main(){ printf("%d\n",function(888)); return 0;}
答案是:6
9999的二进制为1101111000,上面的function函数,利用x&(x-1)这个技巧,得到参数num转化为二进制后含1的个数。共有6个1,所以最后的输出结果为6。我们可以用此式来检查一个无符号数是否是2的幂。
令 x = 10101 011,则 x+1 = 10101100,x&(x+1) = 10101 000,
我们看出 x&(x+1) 将一个二进制数最右边0后的1全置为0。可以用来检测一个无符号整数是否为2^n - 1的形式(包括0和所有位均为1的情况)。析出最右侧的0位,
例:10100111 -> 00001000析出最右侧的1位,如果都没有则生成位均为0的数。
-x 的算法是 对x取反,再加1。 对 x = 01011000,-x = 10101000,x&(-x) = 00001000,即01011000 -> 00001000当x不为0时,x和-x必有一个为正。设x为正。
转载地址:http://tluoi.baihongyu.com/