基础算法(12) —— 位运算

位运算两种简单操作

1. 求n的二进制表示中第k位是多少。

步骤： ①先把第k位移到最后一位 用 n>>k; ②看个位是多少n>>k&1

#include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; int main() { int n = 10; for(int k = 3; k >= 0; k--) cout << (n >> k & 1) << endl; return 0; }

2. 返回n的最后一位1：lowbit(n) = n & -n;

lowbit(x)：返回x的最后一位1 假设： ①x = 1010 则lowbit(x) = 10; ②x=101000 则lowbit(x) = 1000;

x&-x 一个数的负数，是补码的概念，补码是 取反+1

$\ast$ 记忆补码的l两个小技巧①从右边开始找到第一个1，这个1左边的数全部取反。②0-原数 = 补码

在二进制里面 -x == ~x+1 则x&-x = x & (~x+1)

例题： Acwing 801. 二进制中1的个数

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

输入格式 第一行包含整数n。

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

输出格式 共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。

数据范围 $1\le n\le 100000$, $0\le 数列中元素的值\le 10^9$ 输入样例：

5 1 2 3 4 5

输出样例：

1 1 2 1 2 #include<iostream> #include<cstdio> using namespace std; int lowbit(int x) {return x & -x;} int main() { int n; cin >> n; while(n--) { int x; cin >> x; int cnt = 0; while(x)//当x不为0的时候 { x -= lowbit(x);//每次减去x的最后一位1 cnt++; } printf("%d ",cnt); } return 0; }