x&(x-1)和x&(-x)的讲解

x&(x-1)这个表达式有两个作用：

1、去掉x最右边的一个1(二进制)

2、判断一个整数是不是2的n次幂

int func(x) 
{ 
    int countx =; 
    while(x) { 
        countx ++; 
        x = x&(x-); 
    } 
    return countx; 
}
           

这道微软的笔试题，显而易见的是，求x中二进制里面1的个数。

结果其实没什么，重要的是我们要知道为什么x&(x-1)为什么可以达到这样的效果。

关键在于(x-1)一定会把最低位的一个1扯下水，因为需要减1啊。再按位&一下，只会关系到最低的1，自然就可以了。

再看看(x&(-x))是个什么东西，这个的作用就是求出2^p(其中p: x 的二进制表示数中， 右向左数第一个1的位置)

有什么用呢？

在树状数组里面会用到。

还有呢？

int main(){  
   int x;
   while(cin>>x){
    cout<<(x&(x-))<<endl;

    int t=x&(-x);
    cout<<(x^t)<<endl;
   }
    return ;  
}  
           

没有发现吗？

这两个输出都是一样的结果。为什么呢？