2021年的 CSP-j 初賽又掛掉了
比去年更慘
一題題的來(lái)分析一下吧
第一題是位運(yùn)算題
直接就有點(diǎn)沙雕了

語(yǔ)句：for (; x; x &= x - 1) ret++; 題解說(shuō)這個(gè)ret 記錄的就是 x的二進(jìn)制表示中 1 的個(gè)數(shù)，為什么呢？

分析：

功能：將x轉(zhuǎn)化為2進(jìn)制，看含有的1的個(gè)數(shù)。
每執(zhí)行一次x = x&(x-1)，會(huì)將x用二進(jìn)制表示時(shí)最右邊的一個(gè)1變?yōu)?，因?yàn)閤-1將會(huì)將該位(x用二進(jìn)制表示時(shí)最右邊的一個(gè)1)變?yōu)?。

當(dāng)二進(jìn)制數(shù)減1時(shí)，處在最后的一個(gè)位會(huì)減少1，
如果這位本身就是1，那么直接變成0：如10101-->10100;
但如果最后一個(gè)是0，那么套用從上一位借一個(gè)的原則：如10100-->10011;

到這里發(fā)現(xiàn)，相當(dāng)于從右往左的第一個(gè)1會(huì)讓剩下的所有0再變成1；相當(dāng)于把這一個(gè)減的操作從這一個(gè)1處截?cái)唷?yīng)為當(dāng)前是0時(shí)只會(huì)往上一個(gè)1位去借，那么這一位是1時(shí)往下借，后面一定全部是0；然后我們進(jìn)行和原來(lái)一個(gè)數(shù)的與操作，就會(huì)使得這一個(gè)1連同其后的所有位變成0，而更高的位數(shù)不會(huì)受到影響；

so，一次消去一個(gè)1，從右到左消去所有，就實(shí)現(xiàn)了計(jì)算總數(shù)。

每次循環(huán)，執(zhí)行一次x = x&(x-1)，會(huì)將x用二進(jìn)制表示時(shí)最右邊的一個(gè)1變?yōu)?，同時(shí)count計(jì)數(shù)加1，直到x為0。每次執(zhí)行x = x&(x-1)，假設(shè)x的二進(jìn)制最右邊的1在第k位，則其第0 ~ 1-k位全部為0。而x-1，則是第 0 ~ 1-k位全部變?yōu)?，而第k位為0。二者按位與，則第0 ~ k位全部變?yōu)?。

利用x&(x-1)表達(dá)式，還可以用來(lái)判斷一個(gè)數(shù)(x)是否是2的n次方。如果一個(gè)數(shù)是2的n次方，那么這個(gè)數(shù)用二進(jìn)制表示時(shí)其最高位為1，其余位全部為0。用程序表示如下：

int func(int x)
{
    if( (x&(x-1)) == 0 )
        return 1;
    else
        return 0;
}

完結(jié)！