一、位运算

我们都知道数据是以二进制形式存储在计算机中的。当我们使用十进制数进行编程时（如 a=10 ）实际上计算机要先进行一步转码，将其化为二进制的形式进行计算。如果在编程的过程中我们可以直接越过转码这一步去操纵二进制形式进行运算，程序运行速度就会变得更快。

位运算的基本符号：

1. &（按位与）

左右两边都是1，答案就是1.（与条件&&的判定是一致的）

0&1 =0;

0&0 =0;

1&0 =0;

1&1 = 1;

7&28 = 4 ( 00111 & 11100 = 00100 )

&运算通常用于二进制取位操作，例如一个数 &1的结果就是取二进制的最末位。

这可以用来判断一个整数的奇偶，二进制的最末位为 0 表示该数是偶数，最末位为 1 表示该数为奇数。

2. |（按位或）

左右两边有 1，答案就是 1（与条件||的判定是一致的）

0|0=0;

0|1=1;

1|0=1;

1|1=1;

7|28=31 ( 00111 | 11100 = 11111 )

| 运算通常用于二进制特定位上的无条件赋值，例如一个数 | 1 的结果就是把二进制最末位强行变为1 。

如果需要把二进制最末位变成 0 ，对这个数 | 1之后再减一就可以了，其实际意义就是把这个数强行变成最近接的偶数。

3. ^（按位异或） —— 左右两边相同为0，不同为1

0^1=1；

1^0=1；

1^1=0；

0^0=0；

7^28 = 27 ( 00111 ^ 11100 = 11011 )

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

^ 运算可以用于简单的加密，

比如原始值int a = 19880516; 密钥 int key =1314520;

进行加密 int data = key^a = 20665500;解密 data^key == a；

^ 运算还可以实现两个值的交换而不需要中间变量。

要记住这么一个知识： a^b^b 一定会重新得到原来的 a

我们分 4 种情况加以讨论：

1^0^0 = (1^0)^0 = 1^0 = 1

1^1^1 = (1^1)^1 = 0^1 = 1

0^0^0 = (0^0)^0 = 0^0 = 0

0^1^1 = (0^1)^1 = 1^1 = 0

a^b^b 运算落实到每一位的运算，都只会是上面的 4 种情况之一，所以，最终一定会重新得到 a 。

有了上面这个知识之后，理解下面这段代码就容易很多的了。

int a,b;
a = 15;
b = 29;
a = a^b;
b = a^b;
a = a^b;

cout<<a<<" "<<b; // 会发现 a 和 b 发生了交换

上面这段代码的精髓在于：不引入第三个变量的前提下，交换 a 和 b 的值。 我们改一下这段代码，引入一下新的变量，去帮助理解。

int a,b;
a = 15;
b = 29;
int a2 = a^b; // 引入新的变量 a2 ，不冲掉原来的 a 的值
int b2 = a2^b; // 所以 b2 = (a^b)^b = a
int a3 = a2^b2; // 所以 a3 = (a^b)^a = b

cout<<a3<<" "<<b2; // 相当于 cout<<b<<" "<<a;

进一步推广这个性质：a 与 b 进行偶数次 ^ 异或运算之后，结果为 a

4. ~（取反）

~运算的定义把内存中的 0 和 1 全部取反，也包括符号位。

运算时要格外小心，你需要注意整数类型有没符号，如果 ~ 的对象是无符号整数（不能表示负数），那么他的值就是它与它的上界限的之差。（参考之前的原码、反码、补码）

例如，我们用 8 个位而二进制数来表达数字（没有符号为），十进制的 35 会被表示为 00100011 ，所以，35 按位取反，得到的是 11011100 ，取反前后的两个数加起来就是 11111111 ，就是 8 为二进制数的上界。换句话说 11011100（取反值）= 11111111（上界） - 00100011（原数）。

这一规律不适合于有符号二进制。

5. 位移运算：

5.1 << 运算（左移运算）

a << b 表示把 a 转为二进制后左移 b 位（在后面添加 b 个 0 ），移位过程中保留 a 的符号位，也就是说，如果 a 是负数，移位之后也是负数。

例如 100 的二进制表示为 1100100，100 左移 2 位后（后面加 2 个零）：

1100100 << 2 = 110010000 = 400；

可以看出，a << b 的值实际上就是 a 乘以 2 的 b 次方（即左移几次等于乘几次 2 ），因为在二进制数后面添加一个 0 就相当该数乘以 2 ，2 个零即 2 的 2 次方等于 4 。通常认为 a << 1 比 a*2 更快，因为前者是更底层一些的操作。因此程序中乘以 2 的操作尽量用左移一位来代替。

5.2 >> 运算（右移运算）

和 << 相似，a >> b表示二进制右移 b 位（去掉末 b 位），左端的符号位不变，符号位后面的空缺插入 0 或者 1，如果 a 的符号位为 0，插入 0， 如果 a 的符号位为 1，插入 1。

相当于 a 除以 2 的 b 次方（取整）（即右移几次除以几次 2，取整数）。我们经常 用 >> 1 来代替 /2，比如二分查找、堆的插入操作等等。想办法用 >> 代替除法运算可以使程序的效率大大提高，效率可以提高 60% 。

int a = 100;
a/4 == a>>2;