一、算法描述
本篇文章介绍位运算,直接从用法方面来介绍。
求第 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
三、题目来源
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
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net