位运算的操作

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

C++ 中常用的位运算操作符有 6 个：

按位与 &

对于相同位，同有则有，一无则无。

即：相同位的两个数字同为 1，则为 1；有一个不为 1，则为 0。

举例

1
2
3

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

则 $5\ \&\ 28$ 为：

1
2
3
4

  00101    // 5
& 11100    //28
-------
  00100    // 4

即 $5\ \&\ 28=4$。

作用

$\&$ 运算常用于二进制的取位操作，可以判断整数的奇偶性（二进制末尾是 0 为偶数，是 1 为奇数）。一个数 $\&\ 1$ 就取二进制下的最后一位。

按位或 |

对于相同位，一有则有，同无则无。

即：相同位的两个数字只要有一个为 1，则为 1；否则为 0。

举例

1
2
3

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

则$5\ \mid\ 28$为:

1
2
3
4

  00101    // 5
| 11100    //28
-------
  11101    //29

作用

$\mid$ 运算常用于二进制下的赋值，一个数 $\mid\ 1$把二进制末尾的数变成 1，即把这个数变成大于或等于原数的最小奇数（$22\ \mid\ 1=23$；$23\ \mid\ 1=23$；$-10\ \mid\ 1=-9$），若要让其变为偶数，把它 $\mid\ 1$后减一即可。

按位异或 ^

对于相同位，不同则有，相同则无。

即：相同位的两个数字不同则为 1；相同则为 0。

举例

1
2
3

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

则$5\wedge 28$为:

1
2
3
4

  00101    // 5
^ 11100    //28
-------
  11001    //25

作用

有趣的是，$\wedge$ 操作的逆运算是其本身，即两次异或同一个数后结果不变：$(a\wedge b)\wedge b=a$。因此，$\wedge$ 可用于简单加密：

若原文为 $123456789$，密钥为 $10086$，加密得密文:

1

123456789 ^ 10086 = 123464307

要解密，再次异或密钥即可：

1

123464307 ^ 10086 = 123456789

按位取反 ~

无则有，有则无。

即：把 1 换成 0，0 换成 1。

举例

1
2

~ 1 = 0
~ 0 = 1

C++中取反运算实例：

1
2
3
4
5
6
7
8
9
10

#include<iostream>
using namespace std;

int main()
{
    unsigned short a = 100;
    a = ~a;
    cout << a << endl;
    return 0;
}

输出 $65435$。

但若运行如下代码：

1
2
3
4
5
6
7
8
9

#include<iostream>
using namespace std;

int main()
{
    unsigned short a = 100;
    cout << ~a;
    return 0;
}

输出 $-101$。

这是因为有符号类型和无符号类型取反效果不同。

左移 <<

$a\ll b$ 把二进制下的 $a$ 后面添加 $b$ 个 0。

举例

1
2
3
4

//（所有数字在十进制下表示）
1 << 2 = 4     // 100
1 << 10 = 1024 // 10000000000
2 << 3 = 16    // 10000

作用

看到例子，你发现了什么？

对！$a\ll n = a\times 2^n$，要计算 $2^n$，可以不用 pow()，用左移运算 $1\ll n$，要快得多。定义常量也可以用左移运算：$1\ll 16-1$可以表示 $65535$。

右移 >>

$a\gg b$ 把二进制下的 $a$ 向右移 $b$ 位，低位舍去，高位补 0。

举例

1
2
3

4 >> 2 = 1
1024 >> 5 = 32
1000 >> 10 = 0

作用

和左移类似，$a\gg b$ 相当于 $\lfloor a\div 2^b\rfloor$（取整），因此可以用 $\gg 1$ 代替 $\div 2$。

完~