位运算¶
前置知识¶
二进制
目标¶
取反，按位与，按位或，按位异或，左移，右移，lowbit操作
取反¶
NOT，~
有符号整数的符号位在 ~ 运算中同样会取反
在二进制表示下，正数和 0 的补码为其本身，负数的补码是将其对应正数按位取反后加一
取反操作符用波浪线"~"表示。值得注意的是此操作符与“逻辑非（!）”操作符不同
C++中，~a
有符号整数
对于无符号整数，数的按位补码，是其在无符号整数范围的中点另一边的“镜像”。例如，对于8位无符号整数，NOT x = 255 - x，可以在图上将其可视化为一条向下的线，相当于从 0 到 255 递增的范围，“翻转”到从 255 到 0 递减的范围。
按位与¶
AND，&
按位与处理两个长度相同的二进制数，两个相应的二进位都为1，该位的结果值才为1，否则为0。
此操作可以被用来检查一个特定的位是1还是0
C++中，a & b
按位或¶
OR，|
按位或处理两个长度相同的二进制数，两个相应的二进位中只要有一个为 1，该位的结果值就为 1。
应用按位或操作可以将二进制数的某一位设为 1
C++中，a | b
按位异或¶
NOR，^
按位异或运算，对等长二进制模式或二进制数的每一位执行逻辑异或操作。操作的结果是如果某位不同则该位为 1，否则该位为 0。
用值的自身对其执行按位异或运算将得到 0
C++中，a ^ b
移位¶
左移使用两个小于符号"<<"表示，右移使用两个大于符号">>"表示
用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。
算数左移：
算数右移：
左移一位，乘以二；右移一位，除以二。
n << m
n >> m
int x = -5;
cout << (x >> 1) << '\n'; // 向下取整，向负方向取整
cout << (x / 2) << '\n'; // 向0取整
判断两个非零数符号是否相同
bool isSameSign(int x, int y) { // 有 0 的情况例外
return (x ^ y) >= 0;
}
交换两个数
void swap(int &a, int &b) { a ^= b ^= a ^= b; }
获取二进制的某一位
int getBit(int a, int b) { return (a >> b) & 1; }
将二进制的某一位，置成0
int unsetBit(int a, int b) { return a & ~(1 << b); }
将二进制的某一位，置成1
int setBit(int a, int b) { return a | (1 << b); }
将二进制的某一位，取反
int flapBit(int a, int b) { return a ^ (1 << b); }
计算绝对值
int Abs(int n) {
return (n ^ (n >> 31)) - (n >> 31);
/* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
需要计算 n 和 -1 的补码，然后进行异或运算，
结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
}
算数右移、逻辑右移¶
算数右移：
在二进制补码表示下，把数字同时向右移动，高位以符号位填充，低位越界后舍弃。
n >> 1，等于 n 除以 2 向下取整， (-3) >> 1 = -2, 3 >> 1 = 1
n / 2，在 C++ 中实现为“除以2向零取整”，(-3) / 2 = -1, 3 / 2 = 1
逻辑右移：
在二进制补码表示下，把数字同时向右移动，高位以 0 填充，低位越界后舍弃
C++语法没有规定右移的实现方式，我们默认右移操作采用算数右移方式实现
lowbit()¶
非负整数 n 在二进制下 “最低位的 1 及其后边所有的 0” 构成的数值
n = 10, 二进制为 \((1010)_2\) ，lowbit(n) = 2
int lowbit(int n) {
return n & -n; // n & (~n + 1)
}
// 运用lowbit操作，可以找出整数二进制表示下的所有是 1 的位
for (int i = 0; i <= 20; i++) H[1 << i] = i; // 预处理
while (n > 0) {
cout << H[n & -n] << ' ';
n -= n & -n;
}
总结¶
NOT，AND，OR，NOR，<<，>>
lowbit操作，n & -n，返回最低位的1及其后边所有的0构成的数值
参考¶
《算法进阶指南》