题解 | #查找输入整数二进制中1的个数# lowbit得到二进制最低位1

lowbit原理

这里最后一位1是指从左往右最后一位，函数lowbit()返回的是包含该1与右边所有0。

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

-x 在计算机内部是以补码方式运算的，即:
-x = ~ x + 1
假设一个二进制数为： 0010101…0010100000
~x 为： 1101010…1101011111
~x + 1 为： 1101010…1101100000
注意到+1操作使得最后一位1及其右边所有数字发生了变化，而左边不变。
此时在和原数字进行&运算，它和原数字在最后一位1左侧全部不同，右侧全部相同。

code

#include<bits/stdc++.h>

using namespace std;

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

int main()
{
    int n;
    for (; cin >> n;) {
        int cnt = 0;
        for (; n; n -= lowbit(n))
            cnt++;
        cout << cnt << endl;
    }
}