2021年的 CSP-j 初赛又挂掉了
比去年更惨
一题题的来分析一下吧
第一题是位运算题
直接就有点沙雕了
语句：for (; x; x &= x - 1) ret++; 题解说这个ret 记录的就是 x的二进制表示中 1 的个数，为什么呢？
分析：
功能：将x转化为2进制，看含有的1的个数。
每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。
当二进制数减1时，处在最后的一个位会减少1，
如果这位本身就是1，那么直接变成0：如10101-->10100;
但如果最后一个是0，那么套用从上一位借一个的原则：如10100-->10011;
到这里发现，相当于从右往左的第一个1会让剩下的所有0再变成1；相当于把这一个减的操作从这一个1处截断。应为当前是0时只会往上一个1位去借，那么这一位是1时往下借，后面一定全部是0；然后我们进行和原来一个数的与操作，就会使得这一个1连同其后的所有位变成0，而更高的位数不会受到影响；
so，一次消去一个1，从右到左消去所有，就实现了计算总数。
每次循环，执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，同时count计数加1，直到x为0。每次执行x = x&(x-1)，假设x的二进制最右边的1在第k位，则其第0 ~ 1-k位全部为0。而x-1，则是第 0 ~ 1-k位全部变为1，而第k位为0。二者按位与，则第0 ~ k位全部变为0。
利用x&(x-1)表达式，还可以用来判断一个数(x)是否是2的n次方。如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位全部为0。用程序表示如下：
int func(int x)
{
if( (x&(x-1)) == 0 )
return 1;
else
return 0;
}
完结！
