|
注：在写题解的时候想查一下位运算的用法，突然发现自己没有位运算的pdf文件，于是就把上次讲课的PPT的内容重新整理了一下（本篇内容结合了网上诸多大佬对于位运算的介绍，在这里对各位大佬表示感谢）
位运算
C++的几种常见位运算
一、按位与(a & b)：
法则：两者的相同位都为 1，则结果中该位为 1；否则结果中该位为 0
0&0=0，0&1=0，1&0=0，1&1=1
例：12 & 6 = 4
12：1 1 0 0
6：0 1 1 0
——————
4：0 1 0 0
与运算的用途：
(1）清零
如果想将一个单元清零，即使其全部二进制位为0*，只要与一个各位都为零的数值相与，结果为零。
(2)取一个数的指定位
比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=00001111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。
(3)判断奇偶
只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。
二、按位或(a | b)：
法则：两者相同位中有一个为 1，则结果中该位为 1；否则结果中该位为 0
0|0=0，0|1=1，1|0=1，1|1=1
例：12 | 6 = 14
12：1 1 0 0
6：0 1 1 0
——————
14：1 1 1 0
或运算的用途：
(1)常用来对一个数据的某些位设置为1
比如将数 X=1010 1110 的低4位设置为1，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=00001111，然后将X与Y进行按位或运算（X|Y=1010 1111）即可得到。
三、按位异或( a^ b)：
法则：两者相同位的值若不同，则结果中该位为 1；否则结果中该位为 0
0 ^ 0=0，0 ^ 1=1，1^ 0=1，1^1=0
例：12 ^ 6 = 10
12：1 1 0 0
6：0 1 1 0
——————
10：1 0 1 0
异或的几条性质:
1、交换律
2、结合律 (a^ b)^c == a^ (b^c)
3、对于任何数x，都有 x^ x=0，x^0=x
4、自反性: a^ b^ b=a^0=a；
异或运算的用途：
1）翻转指定位
比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=00001111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。
2）与0相异或值不变
例如：1010 1110 ^ 0000 0000 = 1010 1110
3）交换两个数
举例void Swap(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;}}
四、按位取反(~a)：
法则：该数中 0的位置变为 1；1 的位置变为 0
取反运算的用途：
1）使一个数的最低位为零
使a的最低位为0，可以表示为：a & ~ 1。~1的值为 1111 1111 1111 1110，再按”与”运算，最低位一定为0。因为” ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。
五、按位左移(a<< b)：
法则：将该数 a左移 b 位，正数左移后为正数，负数左移后为负数
例：3 << 2 = 12
3：0 0 1 1
12：1 1 0 0
a << b = a × 2b
六、按位右移(a>> b)：
法则：将该数 a 右移 b位，正数右移后为正数，负数右移后为负数。不论正负，都下取整
例：13 >> 2 = 3
13：1 1 0 1
3：0 0 1 1
a >> b = a / 2b
七、非 !a：
法则：该数是 0则为 1 ；否则为 0
例：!0 = 1
? !1 = 0
? !2 = 0
八、各种运算符优先级
-,!,~> *,/,% > >>,<< > >,<,>=,<= > ==,!= > & > ^ > | > && > || > 问号表达式 > 赋值语句
九、负数表示（-x = ~x + 1）
十、位运算常用技巧
将 x 第 i 位取反：x ^= 1 << i
将 x 第 i 位制成 1：x |= 1 << i
将 x 第 i 位制成 0：x &= -1 ^ 1 << i 或 x &= ~(1 << i)
取 x 对 2 取模的结果：x & 1
取 x 的第 i 位是否为 1：x & 1 << i 或 x >> i & 1
取 x 的最后一位：x & -x
取 x 的绝对值：(x ^ x >> 31) - (x >> 31) （int 型）
判断 x 是否不为 2的整次方幂：x & x – 1
判断 a 是否不等于 b：a != b , a – b , a ^ b
判断 x 是否不等于 ?1：x != -1 , x ^ -1 , x + 1 , ~x
|