1. 位运算概述

在现代计算机中，所有数据都以二进制形式存储，即 0 和 1 两种状态。计算机对二进制数据进行的运算（如加、减、乘、除）被称为位运算，即对二进制数的每一位进行操作的运算。

为了更好地理解位运算，举个简单的例子：假设我们有如下代码进行两个整数的加法运算：

int a = 35;
int b = 47;
int c = a + b;

计算机会将这两个整数转换为二进制形式，然后进行加法运算：

35:  0010 0011
47:  0010 1111
----------------
82:  0101 0010

因此，与直接使用 +、-、*、/ 运算符相比，合理运用位运算可以显著提高代码在机器上的执行效率。

2. 位运算概览

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
| 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，高位补0或符号位补齐

3. 按位与运算符（&）

定义：对参与运算的两个数据的二进制位进行"与"运算。

运算规则：

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

总结：只有两位同时为1时，结果才为1，否则结果为0。

例如：3 & 5 即 0000 0011 & 0000 0101 = 0000 0001，因此 3 & 5 的值为1。

注意：负数按补码形式参与按位与运算。

用途：

  1. 清零：如果想将一个单元清零，只要与一个各位都为零的数值相与，结果为零。
  2. 取一个数的指定位：例如，取数 X = 1010 1110 的低4位，只需另找一个数 Y = 0000 1111，然后 X & Y = 0000 1110 即可得到 X 的指定位。
  3. 判断奇偶：通过判断最未位是0还是1来决定奇偶，可以用 if ((a & 1) == 0) 代替 if (a % 2 == 0) 来判断 a 是否为偶数。

4. 按位或运算符（|）

定义：对参与运算的两个对象的二进制位进行"或"运算。

运算规则：

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

总结：只要有一个为1，其值为1。

例如：3 | 5 即 0000 0011 | 0000 0101 = 0000 0111，因此 3 | 5 的值为7。

注意：负数按补码形式参与按位或运算。

用途：

  1. 设置某些位为1：例如，将数 X = 1010 1110 的低4位设置为1，只需另找一个数 Y = 0000 1111，然后 X | Y = 1010 1111 即可得到。

5. 异或运算符（^）

定义：对参与运算的两个数据的二进制位进行"异或"运算。

运算规则：

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

总结：相应位相同为0，相异为1。

性质：

  1. 交换律
  2. 结合律： (a ^ b) ^ c == a ^ (b ^ c)
  3. 对于任何数 x，都有 x ^ x = 0，x ^ 0 = x
  4. 自反性：a ^ b ^ b = a ^ 0 = a

用途：

  1. 翻转指定位：例如，将数 X = 1010 1110 的低4位翻转，只需另找一个数 Y = 0000 1111，然后 X ^ Y = 1010 0001 即可得到。
  2. 与0相异或值不变：例如 1010 1110 ^ 0000 0000 = 1010 1110
  3. 交换两个数：
void Swap(int &a, int &b) {
if (a != b) {
    a ^= b;
    b ^= a;
    a ^= b;
}
}

6. 取反运算符（~）

定义：对参与运算的一个数据的二进制位进行"取反"运算。

运算规则：

~1 = 1111 1110
~0 = 1111 1111

即：

~1 = -2
~0 = -1

总结：将 0 变 1，1 变 0。

用途：

  1. 使一个数的最低位为零：例如，使 a 的最低位为0，可以表示为：a & ~1。~1 的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。

7. 左移运算符（<<）

定义：将一个运算对象的各二进制位全部左移若干位，高位丢弃，低位补0。

例如，设 a = 1010 1110，a = a << 2 将 a 的二进制位左移2位、右补0，即得 a = 1011 1000。

若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

8. 右移运算符（>>）

定义：将一个数的各二进制位全部右移若干位，高位补0或补符号位，右边丢弃。

例如，a = a >> 2 将 a 的二进制位右移2位，左补0 或补符号位，具体取决于数的正负。

操作数每右移一位，相当于该数除以2。

9. 复合赋值运算符

位运算符与赋值运算符结合，组成新的复合赋值运算符，它们是：

  • &= 例：a &= b 相当于 a = a & b
  • |= 例：a |= b 相当于 a = a | b
  • >>= 例：a >>= b 相当于 a = a >> b
  • <<= 例：a <<= b 相当于 a = a << b
  • ^= 例：a ^= b 相当于 a = a ^ b

运算规则与前述的复合赋值运算符的运算规则相似。

不同长度的数据进行位运算：

如果两个不同长度的数据进行位运算，系统会将二者按右端对齐，然后进行位运算。

以"与运算"为例说明如下：

在C语言中，long 型占4个字节，int 型占2个字节。如果一个 long 型数据与一个 int 型数据进行"与运算"，右端对齐后，左边不足的位按以下三种情况补足：

  1. 如果整型数据为正数，左边补16个0。
  2. 如果整型数据为负数，左边补16个1。
  3. 如果整型数据为无符号数，左边也补16个0。

例如：

long a = 123;
int b = 1;
long result = a & b;
long a = 123;
unsigned int b = 1;
long result = a & b;