位运算的操作

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

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

含义运算符举例英文
按位与$a\ \&\ b$and
按位或$a\ \mid\ b$or
按位异或$a\wedge b$xor
按位取反$\sim a$not
左移$a \ll b$shl
右移$a \gg b$shr

按位与 &

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

即:相同位的两个数字同为 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$。


位运算的应用https://blog.xecades.xyz/articles/BitwiseOperationUsage

完~

本文作者:Xecades

本文链接:https://blog.xecades.xyz/drafts/BitwiseOperation.html

文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。

评论