GroupBlog

x&(x-1)

现在令 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。

？？？
我们看下面程序会输出什么
？？？

#include<stdio.h>
int 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&(x+1)

令 x = 10101 011，则 x+1 = 10101100，x&(x+1) = 10101 000，
我们看出 x&(x+1) 将一个二进制数最右边0后的1全置为0。可以用来检测一个无符号整数是否为2^n - 1的形式(包括0和所有位均为1的情况)。

(~x)&(x+1)

析出最右侧的0位，
例：10100111 -> 00001000

x&(-x)

析出最右侧的1位，如果都没有则生成位均为0的数。
-x 　的算法是　对x取反，再加1。
对 x = 01011000，-x = 10101000，x&(-x) = 00001000，即01011000 -> 00001000

当x为0时，x&(-x) 即 0 & 0，结果为0；
当x不为0时，x和-x必有一个为正。设x为正。
1. 当x为奇数时，最后一位为1，取反加1没有进位，故x和-x除最后一位外前面的位正好相反，按位与结果为0，最后一位都为1，故结果为1。
2. 当x为偶数，且为2的m次方（m>0）时，x的二进制表示中只有一位是1（从右往左的第m+1位），其右边有m位0，左边也都是0（个数由表示x的字节数决定），故x取反加1后，从右到左第有m个0，第m+1位及其左边全是1。这样，x& (-x) 得到的就是x。
3. 当x为偶数，却不为2的m次方的形式时，可以写作x= y * (2^k)。其中，y的最低位为1。实际上就是把x用一个奇数左移k位来表示。这时，x的二进制表示最右边有k个0，从右往左第k+1位为1。当对x取反时，最右边的k位0变成1，第k+1位变为0；再加1，最右边的k位就又变成了0，第k+1位因为进位的关系变成了1。左边的位因为没有进位，正好和x原来对应的位上的值相反。二者按位与，得到：第k+1位上为1，左边右边都为0。结果为2^k，即x中包含的2的最大次方的因子。比如x=32(100000)时，其中2的最大次方因子为2^5，结果为32；x=28(11100)时，2的最大次方因子为2^2，结果为4。