一
位运算概述
位运算是直接对内存中的二进制位进行操作的运算，是底层编程和高性能计算常用的技术。C++提供了6种位运算符：
-
&：按位与（与运算） -
|：按位或（或运算） -
^：按位异或（异或运算） -
~：按位取反（取反运算） -
<<：左移（左移运算） -
>>：右移（右移运算）
【位运算符的优先级】
-
最高优先级：~（按位取反），它是单目运算符； -
其次是：<<（左移）、>>（右移）； -
接着是：&（按位与）； -
再接着是：^（按位异或）； -
最后是：|（按位或）。
二位运算符详解
一、按位与 (&)：
【运算规则】两位同时为1结果才为1，否则结果为0。
【示例程序】
- int a = 5; // 0101
- int b = 3; // 0011
- int c = a & b; // 0001 (1)
【应用案例】
1、判断奇偶：若 (n & 1) == 0，则 n 为偶数；
2、清零特定位：n & ~(1 << k)，将第 k 位清零。
二、按位或 (|)：
- int a = 5; // 0101
- int b = 3; // 0011
- int c = a | b; // 0111 (7)
三、按位异或 (^)：
- int a = 5; // 0101
- int b = 3; // 0011
- int c = a ^ b; // 0110 (6)
四、按位取反 (~)：
- int a = 5; // 00000000 00000000 00000000 00000101
- int b = ~a; // 11111111 11111111 11111111 11111010 (-6)
11111111 11111111 11111111 11111010 表示的数是 -6，需要从补码表示法（Two's Complement）的角度来分析。2、对原码取反，得到反码，如下：
- 00000000 00000000 00000000 00000110
3、反码加1，得到 -6 的补码（即 -6 的二进制表示）：
- 11111111 11111111 11111111 11111001
- 11111111 11111111 11111111 11111010
五、左移 (<<)：
- // 将 a 的所有二进制位向左移动 1 位
- int a = 5; // 0101
- int b = a << 1; // 1010 (10)
六、右移 (>>)：
- // 将 a 的所有二进制位向右移动 1 位
- int a = 10; // 1010
- int b = a >> 1; // 0101 (5)
- int b = a >> 2; // 0010 (2)（向下取整）
- int a = -8; // 二进制: 1111...1111000 (32位)
- int b = a >> 1; // 二进制: 1111...1111100 (-4)
- // 左侧补 1 而非补 0
三位运算经典案例
例题-1、统计二进制中1的个数：
手动计算一下，很容易理解统计算法。
- # include <bits/stdc++.h>
- using namespace std;
- int count_1(int n) { // 统计二进制中 1 的个数
- int cnt = 0; // 声明计数变量 cnt
- while (n) { // 只要不为 0，持续计数
- cnt++; // 每循环一次，计数器加 1
- n &= (n - 1); // 去除最低位的 1
- }
- return cnt; // 返回计数结果
- }
- int main() {
- int n;
- cin >> n;
- cout << count_1(n) << endl;
- return 0;
- }
例题-2、判断一个正整数是否为2的幂：
观察2的幂的二进制表示特征，很容易这么判断的原因。
- # include <bits/stdc++.h>
- using namespace std;
- // 判断一个正整数是否为2的幂
- bool isPowerOfTwo(int n) {
- return (n > 0) && ((n & (n-1)) == 0);
- }
- int main() {
- int n;
- cin >> n;
- cout << isPowerOfTwo(n) << endl;
- return 0;
- }
例题-3、交换两个变量的值：
在纸上写一写，算一算例题，理解异或运算的交换律和结合律。
- # include <bits/stdc++.h>
- using namespace std;
- // 交换两个变量的值
- void jiao_huan(int &a, int &b) {
- a ^= b;
- b ^= a;
- a ^= b;
- return ;
- }
- int main() {
- int a, b;
- cin >> a >> b;
- jiao_huan(a, b); // 交换a、b的值
- cout << a << " " << b << endl;
- return 0;
- }
例题-4、查找出现奇数次的数字（其余数都出现偶数次）：
- # include <bits/stdc++.h>
- using namespace std;
- int nums[10];
- int main() {
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) cin >> nums[i];
- int ret = 0; // ret存储最终结果，默认为0
- for (int num : nums) { // 遍历每个数
- ret ^= num; // 将遍历到的数与ret执行异或运算
- }
- cout << ret << endl; // 最终ret中的结果就是出现奇数次的数
- return 0;
- }
异或运算的交换律和结合律的灵活运用。
注意：本案例只适用于仅一个数出现奇数次，其它数都出现偶数次的情况；如果有多个数出现奇数次，无法直接使用该方法。
例题-5、位掩码权限系统：
- const int READ = 1 << 0; // 0001
- const int WRITE = 1 << 1; // 0010
- const int EXEC = 1 << 2; // 0100
- // 设置权限
- int permissions = READ | WRITE; // 0011
- // 检查权限
- bool canRead = permissions & READ;
- bool canExec = permissions & EXEC;
- // 添加权限
- permissions |= EXEC;
- // 移除权限
- permissions &= ~WRITE;
Linux系统的权限控制就是这么设定的，只不过在此基础上增加以下三种粒度不同的权限控制：文件拥有者 (User)、所属组 (Group) 和 其他用户 (Others)。
