位运算算法总结

知识概览

如何求n的二进制表示中第k位是几？

1.先把第k位移到最后一位：n >> k

2.看个位是几：x & 1

综合得到：n >> k & 1返回的是n的二进制表示中第k位

例题展示

题目链接

https://www.acwing.com/problem/content/803/

题解

用到lowbit(x) = x & -x这个公式，它返回的是x的最后一个1以及后面的二进制数字。

代码

#include <iostream>

using namespace std;

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

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        
        int res = 0;
        while (x) x -= lowbit(x), res++;  // 每次减去x的最后一位1
        
        cout << res << ' ';
    }
    
    return 0;
}