（坚持每天写算法）算法学习与复习part1基础算法1-13——位运算

　　最近确实有在写算法，在写dp，之前学的时候不全，被计数，树型等dp折磨了一下。

　　位运算是将重点放在数字的位上，通常作为辅助行动，比如状态dp，有的时候是为了节省时空复杂度而使用的。

　　这是今天的题目：

 　　位运算应用的情况除了上面讲的，还有单纯的位问题，上面的题目就是一个例子。

　　这道题的思路运用到了一个lowbit运算，lowbit运算是获取一个二进制数中最右边的1所对应的数值（十进制），例如，对于二进制数101100（十进制数为44），它的lowbit为100（十进制数为4）。这是因为最右边的1所对应的位是第三位，对应的数值为4，因此lowbit(x) = 4。

　　lowbit运算有一个公式：lowbit(x) = x & (-x)

　　lowbit的原理，说真的我不是很在意它的原理，因为这种感觉是结果（或者说是规律）比较重要一点，不过这里还是贴出大佬的解释：

　　1.对于x的二进制表示中，k位之右的数，它们在x中都对应了0，所以对于这部分的数值，x & (-x) = 0。
　　2.对于x的二进制表示中，k之左的数值，它们在x中对应了0 或者 1，而在-x的二进制表示中，他们对应 1 或 0， 与 x 的数值相反（0对1， 1对0）。因此，在进行按位与运算时，x中第k位之左的数值能够与-x中的相应位数值得到0。
　　3.对于第 k 位来说，x 的第k位为1，-x的第k为也为1，因此，在进行按位与运算时，x中第k位的数值能够与-x中的第k为数值得到1。
　　4.因此 x & (-x) = 2^k

　　当知道了lowbit运算后，这道题也很容易写了，计算到最后面的1后将它消除掉，这样子最后面的1就会变成前面的1，就可以计算了。

　　这里是c++代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int main(){
    int n;
    int data;
    cin >> n;
    
    while(n --){
        int s = 0;
        cin >> data;
        for(int i = data ;i ; i -= i & -i) s ++;
        cout << s << " " ;
    }
}

　　这里是我的打卡代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//下意识直接使用了数组，看了一下题解改了一下
using namespace std;

//y总说的 i & (-i) == i & (~i + 1),其实个人觉得很奇怪，假设i是0000 0011（3），正数的反码是他本身，再加1，那么应该是0000 0100,是4，而不是1011（-3）
        //或者是（以原码的角度来看是）也不是1110（-3）（其实应该按照八位来算，但是只要是负数，那么首位就是1，那也不符合

        //负数的话，11111111是-1，除了符号位都取反，再加1，算出来其实是100000001，补码的角度来看也不是1.
        //计算机中的，都是按照补码来存储的吧，至少C++应该是

        //唯一的解释是，这个取反号，不分谁是符号位，而是直接全部取反，不要再思考什么“正数的反码是他本身”，他这个号就是一视同仁
        //按这样想，负整数的都是成立的（）（注意，数的表示都是按照补码）
        //很玄乎，减去lowbit操作后面就可以知道i的个数了，个人表示这是不是就是一种规律呢
        //怎么当时傻傻的，减去lowbit操作就可以知道i的个数，原因可以用二进制减一下就知道了。
        //https://zhuanlan.zhihu.com/p/118432554


int main(){
    int n;
    cin >> n;
    while(n --){
        int x , s=0;
        cin >> x;

        for(int i = x ; i ;i -= i & -i ) s ++;
        //建议背一下模板

        cout << s  <<" ";
    }
    return 0;
}

　　参考链接：https://zhuanlan.zhihu.com/p/118432554

　　　　　　　 AcWing 801. 二进制中1的个数--海绵宝宝 - AcWing