第 22 节：位运算
课程目标：
- 理解基本的位运算符及其用法。
- 掌握位运算在实际编程中的应用。
- 能够使用位运算解决常见问题。
1. 课程导入 1
- 位运算的意义：本质性，二是计算机底层就是二值逻辑
2. 位运算符介绍 3
按位与 (&)
cpp#include <iostream> using namespace std; int main() { unsigned int a = 3; // 11 in binary unsigned int b = 5; // 101 in binary cout << "a & b: " << (a & b) << endl; // 输出 1 (001 in binary) return 0; }- 按位或 (|)
cpp#include <iostream> int main() { int a = 2; // 10 in binary int b = 6; // 110 in binary std::cout << "a | b: " << (a | b) << std::endl; // 输出 6 (110 in binary) return 0; }按位异或 (^)
cpp#include <iostream> int main() { int x = 12; // 1100 in binary int y = 25; // 11001 in binary std::cout << "x ^ y: " << (x ^ y) << std::endl; // 结果为 21 (10101 in binary) return 0; }按位取反 (~)
cpp#include <iostream> int main() { unsigned int n = 1; // 00000001 in binary std::cout << "~n: " << (~n) << std::endl; // 注意：结果取决于系统位数 return 0; }左移 (<<)、右移 (>>)
cpp#include <iostream> int main() { int z = 1; // 00000001 std::cout << "z << 2: " << (z << 2) << std::endl; // 00000100 (4 in decimal) std::cout << "z >> 1: " << (z >> 1) << std::endl; // 00000000 (0 in decimal) return 0; }
3. 应用示例与实践 9
使用位运算进行权限控制
cpp#include <iostream> void checkPermission(int permissions, int requiredPermission) { if (permissions & requiredPermission) { std::cout << "Permission granted." << std::endl; } else { std::cout << "Permission denied." << std::endl; } } int main() { int userPermission = 0b0101; // 读和写权限 checkPermission(userPermission, 0b0001); // 检查读权限 checkPermission(userPermission, 0b0010); // 检查写权限 return 0; }使用位运算交换两个数
cpp#include <iostream> void swap(int &a, int &b) { a = a ^ b; b = a ^ b; a = a ^ b; } int main() { int x = 4, y = 5; swap(x, y); std::cout << "x: " << x << ", y: " << y << std::endl; return 0; }
4. 深入探讨：位运算的高级用法 4
查找唯一的数字
cpp#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> numbers = {4,1,2,1,2}; std::cout << "The single number is: " << singleNumber(numbers) << std::endl; return 0; }
6. std::bitset 的使用 3
什么是
std::bitset？std::bitset是一个固定大小的位序列，可以像对待数组一样处理位，非常适用于需要位运算的场景。
如何使用
std::bitseta. 初始化和设置位
cpp#include <iostream> #include <bitset> int main() { // 创建一个包含4位的bitset，所有位初始为0 std::bitset<4> bset1; // 通过字符串初始化bitset std::bitset<4> bset2("1011"); std::cout << "bset1: " << bset1 << std::endl; std::cout << "bset2: " << bset2 << std::endl; // 设置某一位为1或0 bset1[1] = 1; // 设置第二位为1 std::cout << "After setting: " << bset1 << std::endl; return 0; }b. 常用操作
cpp#include <iostream> #include <bitset> int main() { std::bitset<4> bset1(9); // 1001 std::bitset<4> bset2(5); // 0101 // 按位逻辑运算 std::cout << "bset1 & bset2: " << (bset1 & bset2) << std::endl; std::cout << "bset1 | bset2: " << (bset1 | bset2) << std::endl; std::cout << "bset1 ^ bset2: " << (bset1 ^ bset2) << std::endl; // 翻转所有位 std::cout << "~bset1: " << (~bset1) << std::endl; // 测试某一位 std::cout << "Is the second bit of bset1 set? " << bset1.test(1) << std::endl; return 0; }c. 转换功能
cpp#include <iostream> #include <bitset> #include <string> int main() { std::bitset<4> bits("1010"); // 转换为字符串 std::string str = bits.to_string(); std::cout << "String representation: " << str << std::endl; // 转换为无符号长整数 unsigned long num = bits.to_ulong(); std::cout << "As unsigned long: " << num << std::endl; // Note: 当bitset的大小超过unsigned long的位数时，会抛出overflow_error try { std::bitset<33> tooLarge(1); tooLarge.to_ulong(); // This will throw } catch(const std::exception& e) { std::cerr << "Error: " << e.what() << std::endl; } return 0; }
课后作业 4
- 作业:
- 使用位运算编写一个程序，该程序能够将一个整数的第n位进行翻转（0变1，1变0）。
cpp
#include <iostream>
#include <bitset>
#include <stdexcept>
template<int Size>
class BitSet {
public:
BitSet(int n) : bits(n) {} // 模板构造函数，无需参数，直接使用模板参数Size
void flip(int n) {
bits.flip(n);
}
bool check(int n) {
return bits.test(n);
}
private:
std::bitset<Size> bits; // 使用模板参数来定义bitset的大小
};
int main() {
try {
BitSet<10> bs(1); // 现在可以用任意的大小来初始化BitSet了
bs.flip(2);
std::cout << "Bit at position 2 is: " << (bs.check(2) ? "set" : "not set") << std::endl;
// 测试越界的情况
bs.check(10); // 这会抛出异常
} catch (const std::exception& e) {
std::cerr << "Exception caught: " << e.what() << std::endl;
}
return 0;
}