基本概念

与(AND)、或(OR)、取反(NOT)、异或(XOR)

右移(>>)k位等价于除2的k次方

左移(<<)k位等价于乘2的k次方

看n的二进制表示中第k位是几

点击查看
1
n的二进制表示中第k位是几（二进制中最后一位是第零位）
1
2
3
方法：①先把第K位移到最后一位  n >> k
	 ②看个位是几  x&1
	结合起来，看n的二进制表示中第k位是几的方法就是：n >> k & 1

例题1：输出n的二进制数

1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;

int main(){
    int n = 10;
    
    for(int k = 3; k >= 0; k--) cout<<(n >> k & 1);//1010
    
    return 0;
}

lowbit()

点击查看
1
2
lowbit(x)：返回一个二进制数，这个二进制数是x的最后一位1
如：1010，返回10；101000，返回1000；

例题1：二进制中1的个数

1
2
3
4
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。
输入格式	第一行包含整数 n。第二行包含 n 个整数，表示整个数列。
输出格式	共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
数据范围	1≤n≤100000,0≤数列中元素的值≤109
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
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;

int lowbit(int x){//二进制-x是二进制x的取反再加一，x&-x就可以得到x的最后一位1
    return x & -x;
}

int main(){
    scanf("%d", &n);
	
    while(n --){
        int x;
        scanf("%d", &x);
        
        int res = 0;
        while(x) x -= lowbit(x), res ++;
        
        printf("%d ", res);
    }
    return 0;
}