位运算
1. 位操作基础
基本的位操作符有与、或、异或、取反、左移、右移这6种，它们的运算规则如下所示：
| 符号 | 描述 | 运算规则 |
|---|---|---|
| & | 与 | 两个位都为1时，结果才为1 |
| | | 或 | 两个位都为0时，结果才为0 |
| ^ | 异或 | 两个位相同为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| « | 左移 | 各位全部左移若干位，高位丢弃，低位补0 |
| » | 右移 | 各位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
注意以下几点：
1． 在这6种操作符，只有~取反是单目操作符，其它5种都是双目操作符。
2． 位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错。
3． 对于移位操作，在微软的VC6.0和VS2008编译器都是采取算术称位即算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。
2. 常用位操作小技巧
1. 判断奇偶
只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if (a & 1 == 0)代替if (a % 2 == 0)来判断a是不是偶数。
下面程序将输出0到100之间的所有奇数。
1
2
3
4
for (i = 0; i < 100; ++i)
if (i & 1)
printf("%d ", i);
putchar('\n');
2. 交换两数
不需要中间变量即可实现
1
2
3
4
5
6
7
void Swap(int &a, int &b) {
if (a != b) {
a ^= b; // 1
b ^= a; // 2
a ^= b; // 3
}
}
这里做一下简单的解析，假设a = 2, b = 3。
注意：以下用a_和b_代表原来的值，也就是2和3。用a’和b’代表新值。
- a ^= b，即表示为 a = a ^ b
- b ^= a，b = b ^ a，根据1可以换算：b = b ^ (a ^ b)，b = b^b^a，由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。也就是说，1，2计算结束之后，a’ = a_ ^ b_ ; b被赋值为2，即b’ = a_
- a = a ^ b，即 a = a’ ^ b’，根据2换算，a = a_ ^ b_ ^ a_; 即a = a_ ^ a_ ^ b_; 最后 a = b_，a 被赋值为3
3. 换算符号
变换符号就是正数变成负数，负数变成正数。
具体方法为：取反后加1
1
2
3
4
5
6
7
8
9
10
11
void func(int& num) {
num = (~num) + 1;
}
int main() {
int a = 10;
int b = -5;
func(a);
func(b);
printf("%d %d\n", a, b); // -10 5
}
4. 求绝对值
位操作也可以用来求绝对值，对于负数可以通过对其取反后加1来得到正数。
因此先移位来取符号位，int i = a » 31;要注意如果a为正数，i等于0，为负数，i等于-1。然后对i进行判断——如果i等于0，直接返回。否之，返回~a+1。完整代码如下：
1
2
3
4
int my_abs(int a) {
int i = a >> 31;
return i == 0 ? a : (~a + 1);
}
如果不用判断呢？进一步的，对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：
1
2
3
4
int my_abs(int a) {
int i = a >> 31;
return ((a ^ i) - i);
}
3. 位操作与字符串加密
在实际开发中，有时会将项目数据save到文件，待使用时重新restore回去，但是现在有个问题，如果是int double等类型，直接save即可，但如果是const char*类型，直接保存在文件，会有风险，因此对字符串进行简单的加密或编码处理显得很有必要。
按位异或操作有一些有趣的性质：
- 如果
a ^ b = c，那么c ^ b = a。也就是说，应用同样的操作两次可以恢复原始数据。 - 对于任何数
x，x ^ 0 = x，x ^ x = 0。
这些性质使得异或操作成为一种非常简单的对称加密方法，既可以用于加密也可以用于解密。
具体操作步骤如下：
- 对字符串中的每一个字符，使用
str[i] ^ CODER_NUMBER来得到加密后的字符。 - 将加密后的字符保存到缓冲区中。
例如，假设CODER_NUMBER为42（十进制）或0x2A（十六进制）
1
2
3
4
5
6
7
8
const char* str = "Hello, World!";
char buffer[100];
int CODER_NUMBER = 42;
for (int i = 0; str[i] != '\0'; ++i) {
buffer[i] = str[i] ^ CODER_NUMBER;
}
buffer[strlen(str)] = '\0'; // 确保以null字符结尾
这样，buffer中就会存储加密后的字符串。
如果要解密，只需再次执行同样的操作：
1
2
3
4
5
6
char decrypted[100];
for (int i = 0; buffer[i] != '\0'; ++i) {
decrypted[i] = buffer[i] ^ CODER_NUMBER;
}
decrypted[strlen(buffer)] = '\0';
这样，decrypted中就会存储解密后的原始字符串。
注意：这种方法虽然简单，但并不安全，只适用于对安全性要求不高的场合。如果需要更高的安全性，应使用更复杂的加密算法。
4. 位操作趣味应用
TODO…