0%

常用位运算

lowbit( )

作用: 获取一个二进制数的 最后一位 1 及以后的数

1
2
3
4
int lowbit()
{
return x & -x;
}

例题:[二进制中 1 的个数](801. 二进制中1的个数 - AcWing题库)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

int n ;

int lowbit( int x)
{
return x & -x; //实现方法:x 与运算 x 的取反
}

int main( )
{
cin >> n ;
for ( int i = 0 ; i < n ; i++)
{
int x ;
cin >> x ;
int res = 0 ;
while (x)
{
x -= lowbit(x); //把最后一位1 及以后的都减去
res ++ ; //计数加一
} //重复
cout << res << ' ' ;
}
return 0 ;
}

求n的第k位数字(二进制)

n >> k & 1