位运算
我们都知道，计算机其实只认得 0 和 1，所有的数据与操作最终都是用二进制来存储和计算的。
位运算（Bitwise Operation） 就是指按二进制来进行的运算，由于位是更底层的表示，因此位运算通常是非常快的，位运算在许多底层操作和性能优化中非常有用。
位运算符
在 C++ 中，一共有 6 种位运算符。
位运算符表示及说明如下表所示：
| 运算符 | 名称 | 说明 |
|---|
A & B | 与 | 两个二进制数对应位都为 1，则该位为 1，否则为 0 |
A | B | 或 | 两个二进制数对应位只要有一个为 1，则该位为 1 |
A ^ B | 异或 | 两个二进制数对应位不同则为 1，否则为 0 |
~ | 取反 | 一元运算符，对一个二进制数按位取反，0 变 1，1 变 0 |
A << n | 左移 | 将一个二进制数的所有位向左移 n 位，右侧补 0 |
A >> n | 右移 | 将一个二进制数的所有位向右移 n 位，右端移出去的舍掉对于无符号数，高位补 0 |
| | |
需要注意，要把位运算与我们前面学过 布尔逻辑运算区分开，布尔逻辑运算也有与、或、异或、非这几种运算，分别用符号 &&、||、!=、! 来表示，其运算结果是 bool 类型值 true 或 false 。
布尔逻辑运算针对的是 bool 类型的值所做的运算，其实对于像 int、long long 这样的整数类型也可以做这些逻辑运算，运算的方式就是将这些整数转换为二进制数表示，然后对二进制数的每一位做运算，因此才有位运算的说法。
举个例子：
先把十进制的 5 和 6 转换成二进制数表示
- 5=101(2)
- 6=110(2)
那 5 & 6 其实就是对二进制数 101(2) 和 110(2) 的每一位做与运算，运算结果为 100(2) 也就是十进制的 4，因此
- 5 & 6 = 100(2) = 4
同样的方式我们也可以对 100110(2) 和 011000(2) 做 or 运算。
int a = 100110 | 011000; // 运算结果为 111110
注意，别把位运算与逻辑运算搞混淆了，比如 5 & 6 与 5 && 6 是两种完全不同的操作。
位运算特殊用法
下面我们来看几个位运算的实际应用示例，这些示例展示了位运算在解决实际问题中的强大之处。
1. 奇偶数判断
在前面，我们都是用取余符号 % 来用作奇偶数判断的
if (n % 2 == 0) // 条件成立则是偶数，否则是奇数
实际也可以换成位运算
if ((n & 1) == 0) // 条件成立则是偶数，否则是奇数
为什么可以这样来判断呢？这是因为 一个数转换成二进制后，最后一位要么是 0，要么是 1，如果是偶数，最后一位一定是 0，如果是奇数，最后一位一定是 1 。
2. 快速计算 2 的幂
位运算中的左移运算（Left Shift）可以用来快速计算 2 的幂。将数字 1 左移 n 位，相当于计算 2n。
示例：
#include <iostream>
using namespace std;
int main() {
int n = 3;
int result = 1 << n; // 结果：2^3 = 8
cout << "2 to the power of " << n << " is: " << result << endl; // 输出8
return 0;
}
3. 使用掩码提取特定位
在某些情况下，我们需要从一个整数中提取特定的位，例如，我们可能只需要一个字节中的某几位。我们可以使用与运算（AND）和掩码来实现这一点。
示例：
假设我们有一个8位的整数，我们希望提取最低的4位。
#include <iostream>
using namespace std;
int main() {
int num = 29; // 二进制：00011101
int mask = 15; // 二进制：00001111
int result = num & mask; // 结果：00001101
cout << "The lowest 4 bits of " << num << " are: " << result << endl; // 输出13
return 0;
}
4. 交换两个数的值
我们可以使用异或运算（XOR）来交换两个整数的值，而无需使用第三个临时变量。这在某些内存受限的情况下非常有用。
示例：
#include <iostream>
using namespace std;
int main() {
int a = 5; // 二进制：0101
int b = 9; // 二进制：1001
// 交换 a 和 b 的值
a = a ^ b; // a 变为：1100
b = a ^ b; // b 变为：0101
a = a ^ b; // a 变为：1001
cout << "After swapping: a = " << a << ", b = " << b << endl; // 输出 a = 9, b = 5
return 0;
}
2. 判断一个数 a 从右边数第 k 位是 0 还是 1
a >> (k - 1) & 1 // 结果是 1，第 n 位就是 1，否则为 0
注：这里的第 k 位是指从右边数第 k 位，数的时候编号是从 1 开始
同样，我们来看看为什么可以这样做。
a >> (k - 1) 表示 a 向右移 k - 1 位，移位后，最右侧的个位就刚刚是原来的第 k 位数字。再与 1 进行与运算，如果最右侧的数字是 1，那结果就应该是 1，如果最右侧的数字是 0，那结果也应该是 0。
例：数字 21 的第 3 位数字是多少？
#include <iostream>
using namespace std;
int main() {
int n = 21;
cout << (n >> 2 & 1) << endl;
return 0;
}
运行结果是：
因此，从右边数第 3 位数字应该是 1 。
验证一下，实际上 21 用二进制表示出来为 10101(2)，从右边数第 3 位确实是 1 。
从这个示例来看，我们还可以找到一种求十进制数转二进制数的简便方法，比如说求 21 的二进制表示应该是多少？
可以用以下代码来实现：
#include <iostream>
using namespace std;
int main() {
int a = 21;
for (int i = 5; i > 0; i--) {
cout << (a >> (i - 1) & 1) << " " ;
}
return 0;
}
运行结果为：
这刚好是数字 21 的二进制表示结果。
3. 将指定位置设置为 1
我们也可以使用位运算将某个数的指定位置设置为 1 。
比如说，前面我们知道 21 的二进制表示为 10101(2)，我们想将其第 k 位设置为 1 ，可以像下面这样：
想一想为什么可以这样来设置呢，可以参考上面第 2 个例子来想一想！
可以把这个功能封装成一个函数，下面是完成后的函数，并用这个函数将数字 21，也就是 10101(2) 的从右往回数第 2 位设置为 1 。
#include <iostream>
using namespace std;
// 将指定位设置为 1
int set_bit_one(int n, int k) {
return (n | 1 << (k - 1));
}
int main() {
int n = 21; // 二进制为 10101
int k = 3; // 要设置为 1 的位置
cout << set_bit_one(n, 2) << endl; // 23， 二进制为 10111
return 0;
}
设置后输出的数字是 23，二进制表示是 10111(2)，可以看到，刚好是第 2 位被设置成 1 了。
4. 将指定位置数据清零
如果指定位置数据为 1，则将指定位置的数据设置为 0；如果不是刚该位置数据不变。
下面是代码是将数字 21 从右往左数第 3 位数字清零。
#include <iostream>
using namespace std;
// 将数字 n 的第 k 位清零
int clear_bit(int n, int k) {
return (n & ( ~(1 << (k-1) ) ) );
}
int main(void) {
int n = 21; // 21 的二进制为 10101
int k = 3;
cout << clear_bit(n, k) << endl; // 输出 17，刚好是 10001
return 0;
}
5. 将指定位置数据取反
指定位置数据为 1 刚更改为 0；指定位置数据为 0 则更改为 1 。
主要是利用了异或运算 ^ 。
#include <iostream>
using namespace std;
// 将数字 n 的指定位置 k 处的数据取反
int toggle_bit(int n, int k) {
return (n ^ (1 << (k-1)));
}
int main() {
int n = 21; // 21 的二进制为 10101
int k = 2;
cout << toggle_bit(n, k) << endl; // 输出 23，二进制是10111
return 0;
}
6. 求整型数的绝对值
这部分内容涉及到数的原码与补码表示，如果不太明白，可以参考关于数的表示这一章节。另外，这里讨论的都是针对的 int 整型来计算的。
对于一个负数来说，它的绝对值刚好是把符号位算在一起取反，再加 1 。因此对于一个负数 a 来说，它的绝对值可以这样来求：
int b = ~a + 1; // b 即为负数 a 的绝对值
下面是求 -5 的绝对值的完整代码
#include <iostream>
using namespace std;
int main() {
int a = -5;
int b = ~a + 1;
cout << b << endl;
return 0;
}
对于一个正数来说，它的绝对值是它本身，我也可以利用位运算来判断一个数是不是负数。
因为 int 类型占 4 个字节，一共 32 位，首位是符号位。因此上面的代码执行后，如果 a 为正数，则 k 等于 0；如果 a 是负数，则 k 等于 1 。
因此对于任意一个整数（无论正负），我们可以写出下面一个函数来得到它的绝对值。
int get_abs(int a) {
int k = a >> 31;
return k == 0 ? a : (~a + 1);
}
下面是一段完整的程序：
#include <iostream>
using namespace std;
int get_abs(int a) {
int k = a >> 31;
return k == 0 ? a : (~a + 1);
}
int main() {
int a, b;
cin >> a >> b;
cout << "a的绝对值是:" << get_abs(a) << endl;
cout << "b的绝对值是:" << get_abs(b) << endl;
return 0;
}
输入数据
输出数据
练习：十进制转二进制
利用位运算将十进制整数转换为二进制
// 利用位运算将十进制转换为二进制
// 并且去除掉结果中的前导 0
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// 将 n 转换为二进制并输出
bool flag = false; // 标记变量，用于跳过前导 0
for (int i = 31; i >= 0; i--) {
int bit = (n >> i) & 1;
if (bit == 1) {
flag = true;
}
if (flag == true) {
cout << bit;
}
}
if (flag == false) {
cout << 0; // 特殊情况，n 为 0 时输出一个 0
}
cout << endl;
return 0;
}
小结
总之，位运算是直接对数据的二进制表示进行操作的一种方式，通常用于处理底层的位级别操作和优化，在实际编程中，如用用得好，能起到四两拔千斤的作用，不过在使用位运算时也需要谨慎，避免数据溢出或损失精度带来的问题。
