当前位置：首页 > news >正文

28 位运算

news 2025/7/29 12:43:46

一、位运算符概述

C++ 提供了六种位运算符，分别是按位与（&）、按位或（|）、按位异或（^）、按位取反（~）、左移（<<）和右移（>>）。
位运算符作用于位，并逐位执行操作。&、 | 和 ^ 的真值表如下所示：
下面将分别介绍这些运算符的使用和规则：

1. 按位与（&）

规则：对两个操作数的对应二进制位进行与运算，只有当两个对应位都为 1 时，结果位才为 1，否则为 0。
示例代码：

#include <iostream>
int main() {int a = 5; // 二进制表示: 0101int b = 3; // 二进制表示: 0011int result = a & b; // 二进制结果: 0001，十进制为 1std::cout << "a & b = " << result << std::endl;return 0;
}

解释：在上述代码中，a 的二进制表示为 0101，b 的二进制表示为 0011。按位与运算时，逐位进行比较，只有第四位（从右往左数）两个操作数都为 1，所以结果的二进制表示为 0001，十进制为 1。

2. 按位或（|）

规则：对两个操作数的对应二进制位进行或运算，只要两个对应位中有一个为 1，结果位就为 1，只有当两个对应位都为 0 时，结果位才为 0。
示例代码：

#include <iostream>
int main() {int a = 5; // 二进制表示: 0101int b = 3; // 二进制表示: 0011int result = a | b; // 二进制结果: 0111，十进制为 7std::cout << "a | b = " << result << std::endl;return 0;
}

解释：a 的二进制表示为 0101，b 的二进制表示为 0011。按位或运算时，逐位比较，只要有一个位为 1，结果位就为 1，所以结果的二进制表示为 0111，十进制为 7。

3. 按位异或（^）

规则：对两个操作数的对应二进制位进行异或运算，当两个对应位不同时，结果位为 1，相同时结果位为 0。
示例代码：

#include <iostream>
int main() {int a = 5; // 二进制表示: 0101int b = 3; // 二进制表示: 0011int result = a ^ b; // 二进制结果: 0110，十进制为 6std::cout << "a ^ b = " << result << std::endl;return 0;
}

解释：a 的二进制表示为 0101，b 的二进制表示为 0011。按位异或运算时，逐位比较，不同位为 1，相同位为 0，所以结果的二进制表示为 0110，十进制为 6。

4. 按位取反（~）

规则：对操作数的每一个二进制位进行取反操作，即 1 变为 0，0 变为 1。
示例代码：

#include <iostream>
int main() {int a = 5; // 二进制表示: 0101int result = ~a; // 二进制结果: 1010（补码表示），十进制取决于具体的编译器和机器std::cout << "~a = " << result << std::endl;return 0;
}

解释：a 的二进制表示为 0101，按位取反后为 1010。在计算机中，整数通常以补码形式存储，所以 ~a 的实际十进制值取决于具体的编译器和机器。

5. 左移（<<）

规则：将操作数的二进制位向左移动指定的位数，右边空出的位用 0 填充。左移 n 位相当于将操作数乘以 2 的 n 次方。
示例代码：

#include <iostream>
int main() {int a = 5; // 二进制表示: 0101int result = a << 2; // 二进制结果: 010100，十进制为 20std::cout << "a << 2 = " << result << std::endl;return 0;
}

解释：a 的二进制表示为 0101，左移 2 位后，右边空出的两位用 0 填充，得到 010100，十进制为 20，相当于 5 * 2^2。

6. 右移（>>）

规则：将操作数的二进制位向右移动指定的位数。对于无符号数，左边空出的位用 0 填充；对于有符号数，左边空出的位用符号位（正数为 0，负数为 1）填充。右移 n 位相当于将操作数除以 2 的 n 次方。
示例代码：

#include <iostream>
int main() {int a = 5; // 二进制表示: 0101int result = a >> 1; // 二进制结果: 0010，十进制为 2std::cout << "a >> 1 = " << result << std::endl;return 0;
}

解释：a 的二进制表示为 0101，右移 1 位后，左边空出的位用 0 填充，得到 0010，十进制为 2，相当于 5 / 2。

二、应用实例

1、判断奇偶性
可以使用按位与运算判断一个整数的奇偶性。如果一个数的二进制表示的最低位为 1，则该数为奇数；如果最低位为 0，则该数为偶数。

#include <iostream>
bool isOdd(int num) {return (num & 1) == 1;
}
int main() {int num = 5;if (isOdd(num)) {std::cout << num << " is odd." << std::endl;} else {std::cout << num << " is even." << std::endl;}return 0;
}

2、交换两个数的值
可以使用按位异或运算交换两个数的值，而不需要使用额外的临时变量。

#include <iostream>
void swap(int& a, int& b) {a = a ^ b;b = a ^ b;a = a ^ b;
}
int main() {int a = 5;int b = 3;std::cout << "Before swap: a = " << a << ", b = " << b << std::endl;swap(a, b);std::cout << "After swap: a = " << a << ", b = " << b << std::endl;return 0;
}

3、找出只出现一次的数字
在“只出现一次的数字”系列题目中，利用按位异或运算的特性可以高效地找出只出现一次的数字。例如，在一个数组中，除了一个元素只出现一次，其余元素都出现两次，通过对数组中所有元素进行异或运算，最终结果就是只出现一次的元素。

#include <iostream>
#include <vector>
int singleNumber(std::vector<int>& nums) {int result = 0;for (int num : nums) {result ^= num;}return result;
}
int main() {std::vector<int> nums = {1, 2, 2, 3, 3};int single = singleNumber(nums);std::cout << "The single number is: " << single << std::endl;return 0;
}

4、计算一个数的二进制表示中 1 的个数
可以使用按位与运算和右移运算来计算一个数的二进制表示中 1 的个数。

#include <iostream>
int countOnes(int num) {int count = 0;while (num) {count += num & 1;num >>= 1;}return count;
}
int main() {int num = 5;int onesCount = countOnes(num);std::cout << "The number of 1s in the binary representation of " << num << " is: " << onesCount << std::endl;return 0;
}

三、练习

1、只出现一次的数字（一）简单
题目描述：给定一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。要求找出那个只出现了一次的元素，并且必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
解题思路：本题的关键在于利用位运算中的异或运算（^）特性。异或运算具有以下性质：
一个数与自身异或结果为 0，例如 a ^ a = 0。
任何数与 0 异或结果为其本身，例如 a ^ 0 = a。
异或运算满足交换律和结合律，即 a ^ b = b ^ a ，(a ^ b) ^ c = a ^ (b ^ c) 。
基于这些性质，我们可以将数组中所有数字依次进行异或操作。由于出现两次的数字会相互抵消（异或为 0 ），最终得到的结果就是只出现一次的那个数字。
2、只出现一次的数字（二）中等
题目描述：给定一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。需要找出并返回那个只出现了一次的元素，并且必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
解题思路：对于本题，我们采用位运算的思路，考虑整数的 32 个二进制位。因为除目标数字外其他数字都出现三次，所以我们可以对数组中所有数的每一位二进制位进行统计，具体来说，对于每一位二进制位，统计数组中所有元素在该位上 1 出现的次数。由于其他数字都出现三次，那么该位上 1 出现的次数对 3 取余的结果，就是目标数字在该位上的值。(如果出现3次，取模为0；只出现一次，取模为1)通过对 32 位二进制位都进行这样的操作，我们就能还原出只出现一次的那个数字。
3、只出现一次的数字（三）困难
题目描述：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。需要找出只出现一次的那两个元素，可以按任意顺序返回答案，并且必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
解题思路:本题的解题思路基于异或运算和分组的思想。首先，将数组中所有元素进行异或操作。根据异或运算的性质，出现两次的元素会相互抵消（异或为 0 ），最终得到的结果是两个只出现一次元素的异或值。
然后，找到这个异或值中从右往左第一个为 1 的位。因为这两个只出现一次的元素在该位上的值不同（异或结果为 1 说明两个操作数该位不同），所以可以根据这一位是 1 还是 0 将原数组分成两组。
最后，分别对这两组元素进行异或操作。由于分组后每组中除了目标元素外其他元素都出现两次，所以每组异或的结果就是对应的那个只出现一次的元素。