一、算法描述

本篇文章介绍位运算，直接从用法方面来介绍。

求第 K 位

  • 将第 \(k\) 位移到最后面。
  • \(&1\) 即可。

所以操作为：n >> k & 1

求最后一个 1（求 1 的个数）

  • \(x\)      =   \(1010…100…0\)

  • ~\(x\)      =   \(0101…011…1\)

  • ~\(x+1\)    =   \(0101…100…0\)

  • \(x\) & (~\(x + 1\)) =  \(0000…100…0\)

  • ~\(x\) 表示 \(x\) 的按位取反操作，例如 \(x\) 是 \(0101\) ，那么 ~\(x\) 就是 \(1010\)。

  • 由于计算机中存储数据都是用补码，所以刚好 ~\(x\) + \(1\) 就是 \(-x\)。

  • 所以求最后一个 \(1\) 的操作为：x & -x

二、题目描述

给定一个长度为 \(n\) 的数列，请你求出数列中每个数的二进制表示中 \(1\) 的个数。

输入格式

第一行包含整数 \(n\)。

第二行包含 \(n\) 个整数，表示整个数列。

输出格式

共一行，包含 \(n\) 个整数，其中的第 \(i\) 个数表示数列中的第 \(i\) 个数的二进制表示中 \(1\) 的个数。

数据范围

\(1≤n≤100000,\)
\(0≤数列中元素的值≤10^9\)

输入样例：

51 2 3 4 5

输出样例：

1 1 2 1 2

三、题目来源 AcWing算法基础课-801.二进制中1的个数四、源代码

#include using namespace std;const int N = 100010;int n;int lowbit(int x){    return x & -x;}int main(){    cin >> n;        while (n -- )    {        int x;        cin >> x;                int res = 0;        while (x)   x -= lowbit(x), res ++ ;                cout << res << ' ';    }        return 0;}