位运算
位操作符
&(与运算)：两个位都是 1 时，结果才为 1，否则为 0。1 0 0 1 1 & 1 1 0 0 1 ----------- 1 0 0 0 1|(或运算)：两个位都是 0 时，结果才为 0，否则为 1。1 0 0 1 1 | 1 1 0 0 1 ----------- 1 1 0 1 1^(异或运算)：两个位相同则为 0，不同则为 1。1 0 0 1 1 ^ 1 1 0 0 1 ----------- 0 1 0 1 0可以看作是无进位加法运算。
~(取反运算)：0 则变为 1，1 则变为 0。~ 1 0 0 1 1 ----------- 0 1 1 0 0<<(左移运算)：向左进行移位操作，高位丢弃，低位补 0。cppint a = 8; a << 3; // 移位前：0000 0000 0000 0000 0000 0000 0000 1000 (8) // 移位后：0000 0000 0000 0000 0000 0000 0100 0000 (64)>>(右移运算)：向右进行移位操作。- 对于无符号数，高位补 0。
- 对于有符号数，高位补符号位（算术右移）。
cppunsigned int a = 8; a >> 3; // 移位前：0000 0000 0000 0000 0000 0000 0000 1000 (8) // 移位后：0000 0000 0000 0000 0000 0000 0000 0001 (1) int a = -8; a >> 3; // 移位前：1111 1111 1111 1111 1111 1111 1111 1000 (-8) // 移位后：1111 1111 1111 1111 1111 1111 1111 1111 (-1)
常见位运算问题
1. 位操作实现乘除法
数
a向右移一位 (a >> 1)，相当于将a除以 2。数
a向左移一位 (a << 1)，相当于将a乘以 2。cppint a = 2; a >> 1; // -> 1 a << 1; // -> 4
2. 位操作交换两数
位操作交换两数可以不需要第三个临时变量，虽然普通操作也可以做到，但位操作的效率更高。
普通操作
cppvoid swap(int &a, int &b) { a = a + b; b = a - b; a = a - b; }位操作
cppvoid swap(int &a, int &b) { a ^= b; b ^= a; a ^= b; }位操作解释：
a ^= b=>a = (a ^ b)b ^= a=>b = b ^ (a ^ b)=>b = (b ^ b) ^ a=>b = 0 ^ a=>b = a(此时b的值变为原始a的值)a ^= b=>a = (a ^ b) ^ a=>a = (a ^ a) ^ b=>a = 0 ^ b=>a = b(此时a的值变为原始b的值)
3. 位操作判断奇偶数
通过判断数的最低位是 0 还是 1 来决定。最低位为 0 是偶数，为 1 是奇数。
if ((a & 1) == 0) {
// 偶数
} else {
// 奇数
}4. 位操作交换符号
将正数变成负数，负数变成正数。
int reversal(int a) {
return ~a + 1; // 整数取反加 1 得到其补码表示的负数；负数取反加 1 得到其原码表示的正数。
}5. 位操作求绝对值
整数的绝对值是其本身，负数的绝对值可以通过对其取反加一求得。首先判断其符号位。
int abs(int a) {
int i = a >> 31; // 获取符号位：正数 i=0，负数 i=-1 (即 0xffffffff)
return i == 0 ? a : (~a + 1);
}上述操作可以进行优化，去除条件判断语句。符号位 i 只有两种情况：i = 0 (正数) 或 i = -1 (负数)。
- 对于任何数与 0 异或都会保持不变。
- 与 -1 (即
0xffffffff) 进行异或相当于对此数进行取反。
因此，可以将三目运算符转换为 ((a ^ i) - i)：
- 当
a为正数时，i = 0，((a ^ 0) - 0) = a - 0 = a。 - 当
a为负数时，i = -1，((a ^ (-1)) - (-1)) = (~a) + 1。
int abs2(int a) {
int i = a >> 31; // 获取符号位
return ((a ^ i) - i);
}6. 位操作进行高低位交换
给定一个 16 位的无符号整数，将其高 8 位与低 8 位进行交换。
示例：
34520的二进制表示：10000110 11011000- 将其高 8 位与低 8 位进行交换，得到新的二进制数：
11011000 10000110 - 其十进制为
55430
实现：
- 将无符号数
a右移 8 位 (a >> 8) 即可得到其高 8 位移到低 8 位，高位补 0。 - 将
a左移 8 位 (a << 8) 即可将低 8 位移到高 8 位，低 8 位补 0。 - 然后将这两个结果进行或操作即可求得交换后的值。
unsigned short a = 34520;
a = (a >> 8) | (a << 8);7. 位操作进行二进制逆序
将无符号数的二进制表示进行逆序。
示例：
- 数
34520的二进制表示：10000110 11011000 - 逆序后则为：
00011011 01100001 - 它的十进制为
7009
在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。
分步交换法：
第一步：以每 2 位为一组，组内进行高低位交换。
交换前： 10 00 01 10 11 01 10 00 交换后： 01 00 10 01 11 10 01 00第二步：在上面的基础上，以每 4 位为 1 组，组内高低位进行交换。
交换前： 0100 1001 1110 0100 交换后： 0001 0110 1011 0001第三步：以每 8 位为一组，组内高低位进行交换。
交换前： 00010110 10110001 交换后： 01100001 00011011第四步：以每 16 位为一组，组内高低位进行交换。
交换前： 0110000100011011 交换后： 0001101101100001
奇偶位交换法： 对于上面的第一步，依次以 2 位作为一组，再进行组内高低位交换，这样处理起来比较繁琐。下面介绍另外一种方法进行处理。先分别取原数 10000110 11011000 的奇数位和偶数位，将空余位用 0 填充：
原数： 10000110 11011000
奇数位： 10000010 10001000
偶数位： 00000100 01010000再将奇数位右移一位，偶数位左移一位，此时将两个数据相或即可达到奇偶位上数据交换的效果：
原数： 10000110 11011000
奇数位右移一位： 01000001 01000100
偶数位左移一位：00001000 10100000
两数相或得到： 01001001 11100100上面的方法用位操作可以表示为：
- 取
a的奇数位并用 0 进行填充可以表示为：a & 0xAAAA - 取
a的偶数位并用 0 进行填充可以表示为：a & 0x5555
因此，上面的第一步可以表示为： a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
同理，可以得到其第二、三和四步为： a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
因此整个操作为：
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);8. 位操作统计二进制中 1 的个数
统计二进制中 1 的个数。一种效率较低的方法是分别获取每个二进制位，然后统计 1 的个数。这里介绍一种高效的方法。
以 34520 为例，我们计算其 a &= (a - 1) 的结果：
- 第一次：
- 计算前：
1000 0110 1101 1000 - 计算后：
1000 0110 1101 0000(最右边的 1 变为 0)
- 计算前：
- 第二次：
- 计算前：
1000 0110 1101 0000 - 计算后：
1000 0110 1100 0000(最右边的 1 变为 0)
- 计算前：
- 第三次：
- 计算前：
1000 0110 1100 0000 - 计算后：
1000 0110 1000 0000(最右边的 1 变为 0)
- 计算前：
我们发现，每次执行 a &= (a - 1) 操作，都会将 a 的二进制表示中最右边的 1 变为 0。因此，可以通过循环执行此操作并计数来统计 1 的个数。
int count = 0;
while (a) {
a = a & (a - 1);
count++;
}贡献者
jiechen