位操作运算符¶

在C语言中，位操作运算符作用于位（bit），即一个整数的二进制表达的0和1。位操作运算符包括以下几种：

名称	符号
左移	<<
右移	>>
按位取反	~
按位异或	^
按位与	&
按位或	\|

注意：以下均以4位int为例，而在实际的C语言环境中，int的位数通常是32位或64位

1. 左移（<<）：右边空位补0¶

将一个数的二进制向左移动指定的位数，右边空位补0
应用：相当于将原数乘以2的n次方
例子：x << n相当于x * 2^n

  1011 << 2 
= 101100
//1011(2) = 11(10)
//1011(2) << 2 = 101100(2) = 44
//11(10) * 2^2 = 44

2. 右移（>>）：左边空位补符号位¶

将一个数的二进制向右移动指定的位数，左边空位补符号位（正数补0，负数补1）
应用：相当于将原数除以2的n次方（对于无符号数是整数除法，对于有符号数是向零截断的除法）
例子：x >> n相当于x / 2^n

  1011 >> 2
= 0010
//1011(2) >> 2 = 0010(2) = 2
//11(10) / 2^2 = 2

3. 按位取反（~）：1变0，0变1¶

对一个数的二进制按位取反，将所有的1变为0，0变为1
注意：按位取反的结果取决于整数的位数，这里假设int是4位的。
应用：~a 等价于 -(a+1)。

证明：~a 等价于 -(a+1)

在计算机中负数以补码形式存储，即其绝对值的反码加1。

对于一个正数 a，要想获得它的负数 -a 只需要取反再加1，即 -a = ~a + 1，则 ~a = -a - 1 = -(a + 1)。
对于一个负数 a，在计算机中存作 a = ~|a| + 1，那么

~a
= ~(~|a| + 1)
= ~(-a - 1 + 1)
= ~(-a)
= -(a + 1)

对于 0，0000 0000 取反得到 1111 1111，这就是 -1 的反码表示。

综上所述，对于有符号整数，~a 的结果可以表示为 -|a + 1|。

4. 按位异或（^）：相同为0，不同为1¶

对两个数的二进制按位异或，两个位相同为0，不同为1
异或（^）是取反（~）的一般情况：a ^ 1111 等价于 ~a，a ^ 0000 等价于 a。
应用：翻转原数某几位。创建一个掩码，其中要翻转的位为1，其他位为0，然后与原数按位异或
原理：1 ^ 1 = 0，0 ^ 1 = 1 (flip)，bit ^ 0 = bit (protect)
例子：要翻转x的第n位（右边第一位为第0位），用 1 << n 创建一个掩码mask（其中第n位为1，其他位为0），然后使用 x ^ (1 << n)

  1011
^ 1100
= 0111
--------------------
  1 << 1  //想翻转1011的右数第2位->1001
= 10 
= 0010    //掩码

  1011    //原数
^ 0010    //掩码
= 1001    //结果

应用：交换两个变量的值，无需临时变量
原理：(a^b)^b = a 且 a^b = b^a

a = a ^ b;
b = a ^ b; // 现在b是原来的a
a = a ^ b; // 现在a是原来的b

a ^= b;
b ^= a;
a ^= b;

设a0=1011, b0=0110
a ^ b = 1011 ^ 0110 = 1101
a->1101
a ^ b = 1101 ^ 0110 = 1011
b->1011 (a0)
a ^ b = 1101 ^ 1011 = 0110
a->0110 (b0)

5. 按位与（&）：两个位都为1时，结果为1¶

对两个数的二进制按位与，只有两个位都为1时，结果才为1
应用：设置原数某几位为0，保持其他位不变。创建一个掩码，其中要设0的位为0，其他位为1，然后与原数按位与
原理：bit & 0 = 0 (clear)，bit & 1 = bit (protect)
例子：要设置x的第n位为0（右边第一位为第0位），用 ~(1 << n) 创建一个掩码mask（其中第n位为0，其他位为1），然后使用 x & ~(1 << n)

  1011
& 1100
= 1000
--------------------
  1 << 1  //想把1011的右数第2位变0->1001
=   10
= 0010
~
= 1101    //mask

  1011    //原数
& 1101    //mask
= 1001    //结果

6. 按位或（|）：两个位中有一个为1，结果就为1¶

对两个数的二进制按位或，只要两个位中有一个为1，结果就为1
应用：设置原数某几位为1，保持其他位不变。创建一个掩码，其中要设1的位为1，其他位为0，然后与原数按位或
原理：bit | 1 = 1 (set)，bit | 0 = bit (protect)
例子：要设置x的第n位为1（右边第一位为第0位），用 1 << n 创建一个掩码mask（其中第n位为1，其他位为0），然后使用 x | (1 << n)

  1011
| 1100
= 1111
--------------------
  1 << 2  //想把1011的右数第3位变1->1111
=  100
= 0100    //mask

  1011    //原数
| 0100    //mask
= 1111    //结果

位运算符的作用¶

在C语言中，位操作运算符可以显著优化算法性能，主要体现在以下几个方面：

提高运算速度：位运算直接在二进制层面上操作，通常比传统的算术运算更快，因为它们可以映射到CPU的单个指令上，减少了CPU的负担。
节省内存空间：位运算可以将多个布尔值或小整数压缩到一个变量中，大大节省内存。例如，一个32位整数可以存储32个布尔值，这种技术在状态管理、资源标记等场景中非常有用。
替代乘除法：位运算可以替代乘法和除法操作。左移（<<）运算相当于乘以2的n次方，而右移（>>）运算相当于除以2的n次方。利用这一特性，可以替代乘法和除法操作，从而提高运算速度。
替代条件判断：某些情况下，位运算可以替代条件判断，从而避免分支带来的性能损失。例如，快速求绝对值时，可以通过位运算消除条件判断。
优化哈希函数设计：通过位运算，可以设计出高效的哈希函数。位运算不仅提高了效率，还增强了哈希函数的混淆能力。
快速取模操作：如果模数是2的幂次方，可以使用位运算来快速取模。例如，x % 8 可以表示为 x & (8 - 1)。
状态压缩：在某些情况下，需要在内存中存储多个布尔值或小范围的整数。通过位运算，可以将这些值压缩到一个或几个整数中，从而显著节省内存空间。
减少除法和取模的运算：使用位操作可以减少除法和取模的运算，提高程序运行的效率。例如，i = 257 / 8; 可以优化为 i = 257 >> 3;。
提高执行效率：位运算能够在不使用分支和复杂算术运算的情况下完成诸如乘法、除法、取模、翻转位等操作。这些操作的执行速度通常比使用传统运算快得多。
位掩码操作：位掩码在很多领域都得到了广泛应用，例如权限控制、状态标志等。通过位掩码，可以高效地进行多个标志位的设置和检查。

通过这些方法，位操作运算符在C语言中被广泛用于性能优化，特别是在对性能要求极高的场景，如嵌入式系统、游戏开发、实时处理系统等。