x&=x-1的理解

状压入门ing

刚开始学状压，从二进制的一些内容开始。

有关二进制补码理论：

https://www.cnblogs.com/lianchenboke/p/5061032.html

基础运算：

https://www.cnblogs.com/lianchenboke/p/5061032.html

#有关x&=x-1（举凡遇到十分钟内理解不了的我都会写写）

简单来说就是用作求二进制里1的个数的：

1  while(x) 
2     { 
3           countx ++; 
4           x = x&(x-1); 
5      } 
6     return countx

关于这个运作的机制：（网上入门级的教程都是有二进制基础才看的懂得，所以做一点抽象的）

简单来说，当二进制数减1时，处在最后的一个位会减少1，如果这位本身就是1，那么直接变成0：

如10101-->10100;

但如果最后一个是0，那么套用从上一位借一个的原则；

如10100-->10011;

到这里我发现了，相当于从右往左的第一个1会让剩下的所有0再变成1；

相当于把这一个减的操作从这一个1处截断，应为当前是0时只会往上1位去借，那么这一位是1时往下借，后面一定全部是0；

然后我们进行和原来一个数的与操作，就会使得这一个1连同其后的所有位变成0，而更高的位数不会受到影响；

so，一次消去一个1，从左到右消去所有，就实现了计算总数。