学步园

【面试题】以下代码结果是多少？

#include <iostream>
using namespace std;

int func(int x)
{
    int count = 0;
    while(x)
    {
        count++;
        x = x&(x-1);
    }
    return count;
}

int main()
{
    cout << func(9999) << endl;
    return 0;
}

每次while循环，执行一次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。

9999转换为二进制为：10011100001111（关于十进制与二进制的转换，参考：十进制与二进制间的相互转换），所以最终输出结果为8。

利用x&(x-1)表达式，还可以用来判断一个数(x)是否是2的n次方。如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位全部为0。

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

int main()
{
    int x = 8;
    printf("%d\n", func(x));
}

假设x为8，其二进制为1000，符合最高位为1，其余位为0。这样x&(x-1)，将唯一的最高位的1置0，所以结果为0，8是2的n次方。

假设x为7，其二进制为0111，不符合最高位为1，其余位为0。x&(x-1)将最右边的1置为0，结果为0110，不等于0，所以7不是2的n次方。