【算法】位运算

应用

求一个数二进制表示中1的个数

利用到了一个数的原码和补码。

一个数的原码和补码按位相与可以得到这个数的最低位的1所表示的数的大小,例如:

一个数11000100,那么其反码是00111011,补码是00111100,那么11000100与00111100相与结果为:00000010

那么一个数的二进制表示中1的个数可以用上述方法反复计算,每次计算出来后就在原书的基础上减去,直至为0为止。

int x;
int cnt = 0;
while(x)
{
    x -= lowbit(x);
    cnt ++;
}

int lowbit(int x)
{
    return x & (-x);
}