大家好，欢迎来到我的第一篇博客
位运算和移位运算作为计算机的基本运算之⼀，其都是对⼆进制位进⾏操作。作为近年算法竞赛笔试较热门的考点，它能够快捷地完成特定的应用。掌握它是⾮常有必要的。
以下是目录：
目录1. 位运算的优先级
C++运算符的具体优先级详见大佬的文章
我们学习位运算时需要牢记的优先级简单说来是（从大到小，从先到后）：
- ~、！
- ***、/ **
- +、-
- <<、>>
- ==、!=
- &
- |
- &&
- ||
2. 左移运算 <<、右移运算>>
2.1 运算规则：
在二进制中表现为将数字整体向左或向右移动n位
1 << 2 == 4 (1)
2 >> 1 == 4 (2)
//二进制的操作表现为
0001 --> 0010 (1)
0010 --> 0001 (2)
//少的位数用0来补，多的位数就吞掉了
在数学上，又有不同的意义
1 << 1 == 2 1*2 == 2 //乘二
1 << 2 == 4 1*2*2 == 4 //乘二的次方
4 >> 1 == 2 4/2 == 2 //整除二
7 >> 2 == 1 7/2/2 == 1 //整除二的次方
//效率比普通运算要高
2.2 应用：快速获取2的次方
观察上文左移运算的数学意义，不难发现
1 >> k ==> 2^k
3. 与运算 &
3.1 运算规则：
1 & 1 == 1
1 & 0 == 0
0 & 0 == 0
// 只有两位都是1才得1
// 只要有0就得0
// 特殊运算律
a & b == b & a
a & 0 == 0
a & a == a
a & (b & c) == (a & b) & c
a & ~a == 0
3.2 应用1：判断2的次方
运行以下代码
int tmp;
while(cin >> tmp){
cout << (tmp &= tmp -1) << ' ';
}
输入：
1 2 3 4 5 6 7 8 9
输出：
0 0 2 0 4 4 6 0 8
通过观察我们发现：
2^k & 2^k-1 == 0
// 原理如下：
010000...
& 001111...
--------------
000000...
3.3 应用2：统计数字二进制形式中有多少个 1
运行以下代码
int tmp;
while(cin >> tmp){
int ans = 0;
while(tmp){
tmp &= tmp-1;
ans ++;
}
cout << ans << ' ';
}
输入：
1 2 3 4 5 6 7 8 9
输出：
1 1 2 1 2 2 3 1 2
通过观察我们发现：
1的二进制：0001 --> 1个1
2的二进制：0010 --> 1个1
3的二进制：0011 --> 2个1
4的二进制：0100 --> 1个1
......
所以：
通过 n &= n-1 并在n!=0时进行计数，可以统计n二进制中1的个数
4. 或运算 |
4.1 运算规则
1 | 1 == 1
1 | 0 == 1
0 | 0 == 0
// 只有两位都是零才得0
// 只要有1就得1
// 特殊运算律
a | b == b | a
a | a == a
a | 0 == a
a | ~a == -1
5. 异或运算 ^
5.1 运算规则：
0 ^ 0 == 0
1 ^ 1 == 0
1 ^ 0 == 1
//相同为0，不同为1
// 特殊运算律
a ^ 0 == a
a ^ a == 0
a ^ b == b ^ a
5.2 应用：交换两数（swap）
运行以下代码：
void Swap(int &a, int &b){
a ^= b;
b ^= a;
a ^= b;
}
int main(){
int n, m; cin >> n >> m;
Swap(n, m);
cout << n << ' ' << m;
return 0;
}
输入：
1 2
输出：
2 1
此应用的原理如下：
a = a ^ b
b = b ^ a = b ^ (a ^ b)
= b ^ b ^ a
= 0 ^ a
= a
a = a ^ b = (a ^ b) ^ a
= a ^ a ^ b
= 0 ^ b
= b
结束啦
这篇文章原本是我的课堂笔记，只是略微补充了一下，内容可能会有错误或不完整的地方，欢迎大家指正
