位运算知识

位运算是一种直接对整数在内存中的二进制位进行操作的运算方式。计算机中的整数是以二进制形式存储的，位运算通过操作这些二进制位来实现高效的计算。位运算通常比普通的算术运算更快，因为它直接作用于硬件层面。

以下是几种常见的位运算符及其功能：

1.按位与（`&`）

• 功能：对两个操作数的每一位进行逻辑与操作。只有当两个操作数的对应位都为1时，结果位才为1，否则为0。

• 示例：
  5 & 3
  5 的二进制表示：0101
  3 的二进制表示：0011
  结果：         0001
  十进制结果：   1
 

2.按位或（`|`）

• 功能：对两个操作数的每一位进行逻辑或操作。只要两个操作数的对应位中有一个为1，结果位就为1，否则为0。

• 示例：
  5 | 3
  5 的二进制表示：0101
  3 的二进制表示：0011
  结果：         0111
  十进制结果：   7
  

3.按位异或（`^`）

• 功能：对两个操作数的每一位进行逻辑异或操作。只有当两个操作数的对应位不同时，结果位才为1，否则为0。

• 示例：
  5 ^ 3
  5 的二进制表示：0101
  3 的二进制表示：0011
  结果：         0110
  十进制结果：   6
  

4.按位取反（`~`）

• 功能：对操作数的每一位进行逻辑取反操作。0变为1，1变为0。

• 示例：
  ~5
  5 的二进制表示：0101
  结果：         1010
  十进制结果：   -6（注意：取反后结果为负数，因为最高位是符号位）
  

5.左移（`<<`）

• 功能：将操作数的二进制表示向左移动指定的位数。左移一位相当于乘以2。

• 示例：
  5 << 1
  5 的二进制表示：0101
  左移一位：     1010
  十进制结果：   10
 

6.右移（`>>`）

• 功能：将操作数的二进制表示向右移动指定的位数。右移一位相当于除以2（向下取整）。

• 示例：
  5 >> 1
  5 的二进制表示：0101
  右移一位：     0010
  十进制结果：   2
  

位运算的用途

1.快速乘除

位移运算可以用来快速实现乘法和除法操作，尤其是乘以或除以2的幂次方。
示例：快速乘以8

int x = 5;
int result = x << 3; // 左移3位，等价于 x * 8
// result = 40

• 解释：左移3位相当于乘以\(2^3=8\)。
示例：快速除以4

int x = 20;
int result = x >> 2; // 右移2位，等价于 x / 4
// result = 5

• 解释：右移2位相当于除以\(2^2=4\)。

2.检查奇偶性

通过按位与操作可以快速判断一个数是奇数还是偶数。
示例：判断奇偶性

int x = 7;
if (x & 1) {cout << "奇数" << endl;
} else {cout << "偶数" << endl;
}
// 输出：奇数

• 解释：`x & 1`的结果为1表示`x`是奇数，为0表示`x`是偶数。

3.位掩码操作

位掩码可以用来设置、清除或检查特定的位。
示例：设置特定位

int x = 0b00001010; // 二进制表示为 10
int mask = 0b00000100; // 二进制表示为 4
int result = x | mask; // 按位或操作
// result = 0b00001110，即 14

• 解释：通过按位或操作，可以将`x`的第2位设置为1。

示例：清除特定位

int x = 0b00001110; // 二进制表示为 14
int mask = ~0b00000100; // 二进制表示为 0b11111011
int result = x & mask; // 按位与操作
// result = 0b00001010，即 10

• 解释：通过按位与操作，可以将`x`的第2位清零。

4.交换变量值

通过异或运算可以不使用临时变量交换两个变量的值。

示例：交换变量值

int a = 5;
int b = 7;
a ^= b; // a = a ^ b
b ^= a; // b = b ^ a
a ^= b; // a = a ^ b
// 现在 a = 7, b = 5

• 解释：

1. `a ^= b`：`a`变为`a ^ b`。

2. `b ^= a`：`b`变为`b ^ (a ^ b)`，即`a`。

3. `a ^= b`：`a`变为`(a ^ b) ^ a`，即`b`。

5.计算2的幂次方

通过左移运算可以快速计算2的幂次方。

示例：计算\(2^8\)

int result = 1 << 8; // 左移8位
// result = 256

• 解释：左移8位相当于\(2^8\)。

6.检查是否为2的幂次方

一个数是2的幂次方当且仅当它只有一个位是1。可以通过`x & (x - 1)`来判断。

示例：检查是否为2的幂次方

int x = 256;
if (x & (x - 1) == 0 && x != 0) {cout << x << " 是2的幂次方" << endl;
} else {cout << x << " 不是2的幂次方" << endl;
}
// 输出：256 是2的幂次方

• 解释：

• 如果`x`是2的幂次方，`x`的二进制表示只有一个1。

• `x - 1`的二进制表示会将这个1变成0，并将后面的位变成1。

• 因此，`x & (x - 1)`的结果为0。

• 需要额外检查`x != 0`，因为0不是2的幂次方。

7.统计二进制中1的个数

可以通过逐位检查或使用内置函数来统计一个数的二进制表示中1的个数。

示例：统计1的个数

int x = 0b10101010; // 二进制表示为 170
int count = 0;
while (x) {count += x & 1; // 检查最低位是否为1x >>= 1; // 右移一位
}
// count = 4

• 解释：逐位检查最低位是否为1，然后右移一位，直到`x`为0。

总结

位运算是一种非常高效的操作方式，尤其在需要处理大量数据或优化性能时非常有用。通过上述示例，你可以看到位运算在快速乘除、奇偶性检查、位掩码操作、变量交换、计算2的幂次方、检查2的幂次方以及统计1的个数等场景中的应用。