位运算
一、算法描述
本篇文章介绍位运算，直接从用法方面来介绍。
求第 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\)
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
三、题目来源
四、源代码
#include <iostream>
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;
}