---
title: "位运算"
description: "从环境准备到 STL，系统学习 C++ 编程的基础知识。"
---
> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.
# 位运算
我们都知道，计算机其实只认得 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` 这样的整数类型也可以做这些逻辑运算，运算的方式就是将这些整数转换为二进制数表示，然后对二进制数的每一位做运算，因此才有**位运算**的说法。
举个例子：
```cpp
5 & 6
```
先把十进制的 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` 运算。
```cpp
int a = 100110 | 011000; // 运算结果为 111110
```
> 注意，别把位运算与逻辑运算搞混淆了，比如 `5 & 6` 与 `5 && 6` 是两种完全不同的操作。
## 位运算特殊用法
下面我们来看几个位运算的实际应用示例，这些示例展示了位运算在解决实际问题中的强大之处。
### 1. 奇偶数判断
在前面，我们都是用取余符号 `%` 来用作奇偶数判断的
```cpp
if (n % 2 == 0) // 条件成立则是偶数，否则是奇数
```
实际也可以换成位运算
```cpp
if ((n & 1) == 0) // 条件成立则是偶数，否则是奇数
```
为什么可以这样来判断呢？这是因为 **一个数转换成二进制后，最后一位要么是 0，要么是 1，如果是偶数，最后一位一定是 0，如果是奇数，最后一位一定是 1** 。
### 2. 快速计算 2 的幂
位运算中的左移运算（Left Shift）可以用来快速计算 2 的幂。将数字 `1` 左移 `n` 位，相当于计算 $2^n$。
示例：
```cpp
#include
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位。
```cpp
#include
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）来交换两个整数的值，而无需使用第三个临时变量。这在某些内存受限的情况下非常有用。
示例：
```cpp
#include
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**
```cpp
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 位数字是多少？
```cpp
#include
using namespace std;
int main() {
int n = 21;
cout << (n >> 2 & 1) << endl;
return 0;
}
```
运行结果是：
```
1
```
因此，从右边数第 3 位数字应该是 1 。
验证一下，实际上 21 用二进制表示出来为 $10101_{(2)}$，从右边数第 3 位确实是 1 。
从这个示例来看，我们还可以找到**一种求十进制数转二进制数的简便方法**，比如说求 21 的二进制表示应该是多少？
可以用以下代码来实现：
```cpp
#include
using namespace std;
int main() {
int a = 21;
for (int i = 5; i > 0; i--) {
cout << (a >> (i - 1) & 1) << " " ;
}
return 0;
}
```
运行结果为：
```
1 0 1 0 1
```
这刚好是数字 `21` 的二进制表示结果。
**3. 将指定位置设置为 1**
我们也可以使用位运算将某个数的指定位置设置为 1 。
比如说，前面我们知道 21 的二进制表示为 $10101_{(2)}$，我们想将其第 k 位设置为 1 ，可以像下面这样：
```cpp
21 | 1 << (k - 1)
```
想一想为什么可以这样来设置呢，可以参考上面第 2 个例子来想一想！
可以把这个功能封装成一个函数，下面是完成后的函数，并用这个函数将数字 `21`，也就是 $10101_{(2)}$ 的从右往回数第 2 位设置为 1 。
```cpp
#include
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 位数字清零。
```cpp
#include
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 。
主要是利用了异或运算 `^` 。
```cpp
#include
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` 来说，它的绝对值可以这样来求：
```cpp
int b = ~a + 1; // b 即为负数 a 的绝对值
```
下面是求 `-5` 的绝对值的完整代码
```cpp
#include
using namespace std;
int main() {
int a = -5;
int b = ~a + 1;
cout << b << endl;
return 0;
}
```
对于一个正数来说，它的绝对值是它本身，我也可以利用位运算来判断一个数是不是负数。
```cpp
int k = a >> 31;
```
因为 `int` 类型占 4 个字节，一共 32 位，首位是符号位。因此上面的代码执行后，如果 `a` 为正数，则 `k` 等于 0；如果 `a` 是负数，则 `k` 等于 1 。
因此对于任意一个整数（无论正负），我们可以写出下面一个函数来得到它的绝对值。
```cpp
int get_abs(int a) {
int k = a >> 31;
return k == 0 ? a : (~a + 1);
}
```
下面是一段完整的程序：
```cpp
#include
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;
}
```
**输入数据**
```
-3 8
```
**输出数据**
```
a的绝对值是:3
b的绝对值是:8
```
## 练习：十进制转二进制
利用位运算将十进制整数转换为二进制
```cpp
// 利用位运算将十进制转换为二进制
// 并且去除掉结果中的前导 0
#include
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;
}
```
## 小结
总之，位运算是直接对数据的二进制表示进行操作的一种方式，通常用于处理底层的位级别操作和优化，在实际编程中，如用用得好，能起到四两拔千斤的作用，不过在使用位运算时也需要谨慎，避免数据溢出或损失精度带来的问题。
Source: https://cppguide.xyz/basic/bits/index.mdx