位运算

位运算简介

程序中所有数字在计算机的内存中都是以二进制形式存储，位运算是直接对二进制位进行操作。

C 语言中的 6 种位运算符：

• & 与
• | 或
• ^ 异或
• ~ 取反
• << 左移
• >> 右移

其中除了取反是单目运算其他都是双目运算（单目运算是指参与运算的变量只有一个，双目为两个以此类推）。

与运算

计算过程是将两个数的二进制值按位对比，对应位的值都为 1，结果位才为 1，否则为 0。

3 & 4

00000011 3 的二进制
& 00000100 4 的二进制

---

00000000 结果是 0

5 & 1

00000101
& 00000001

---

00000001 结果是 1

或运算

计算过程是将两个数的二进制值按位对比，对应位的值有 1 则结果位为 1 ，否则为 0。

9 | 4

00001001 9 的二进制
| 00000100 4 的二进制

---

00001101 结果是 13

异或运算

计算过程是将两个数的二进制值按位对比，对应位的值相同则结果位为 0，否则为 1。（也可以理解为“是不是不一样，肯定则为 1，否定则为 0。”）

9 ^ 4

00001001 9 的二进制
^ 00000100 4 的二进制

---

00001101 结果是 13

取反运算

计算过程是将某个数的二进制值按位取反，对应位的值为 1 则结果位为 0，反之为 1。

~ 00001001 9 的二进制

11110110

左移运算

计算过程是将运算符左边的数的二进制位逐个左移若干位，由运算符右边的数指定移动位数，高位丢弃，低位补 0。

3 << 4 => 00000011 << 4 => 00110000（十进制的48）

右移运算

计算过程是将运算符左边的数的二进制位逐个右移若干位，由运算符右边的数指定移动位数，低位丢弃，高位补 0。

15 >> 2 => 00001111 >> 2 => 00000011 （十进制的3）

说明：对于有符号数，在右移时，符号位将随同移动。当为正数时，最高位补 0，而为负数时，符号位为 1，最高位是补 0 或是补 1 取决于编译系统的规定。

位运算实用技巧

1. & 与运算
   通常用于二进制取位操作。
   例如：一个数 & 1 的结果就是取二进制的最末位，可以用来判断一个整数的奇偶，二进制最末位为 0 表示该数是偶数，最末位为 1 表示该数为奇数。

2. | 或运算
   通常用于二进制特定位上的无条件赋值。
   例如：一个数 | 1 的结果就是把二进制的最末位强行变成 1。如果需要把二进制最末位变成 0，对这个数 | 1 之后再减 1 就可以了，其实际意义就是把这个数强行变成最接近的偶数。

3. ^ 异或运算
   通常用于对二进制的特定位进行取反操作，因为 0 和 1 异或 0 都不变，异或 1 则取反。
   异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 (a ^ b) ^ b = a。

4. ~ 取反
   使用取反运算时要格外小心，你需要注意整数类型有没有符号。如果取反的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用$0000到$FFFF依次表示的。

5. << 左移
   a << b的值实际上是a乘以2的b次方。

6. >> 右移
   a >> b的值实际上是a除以2的b次方（取整）。我们也经常用>> 1来代替div 2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的mod运算，效率可以提高60%。