程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。
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 | 1 & 1 = 1 |
则 $5\ \&\ 28$ 为:
1 | 00101 // 5 |
即 $5\ \&\ 28=4$。
作用
$\&$ 运算常用于二进制的取位操作,可以判断整数的奇偶性(二进制末尾是 0 为偶数,是 1 为奇数)。一个数 $\&\ 1$ 就取二进制下的最后一位。
按位或 |
对于相同位,一有则有,同无则无。
即:相同位的两个数字只要有一个为 1,则为 1;否则为 0。
举例
1 | 1 | 1 = 1 |
则$5\ \mid\ 28$为:
1 | 00101 // 5 |
作用
$\mid$ 运算常用于二进制下的赋值,一个数 $\mid\ 1$把二进制末尾的数变成 1,即把这个数变成大于或等于原数的最小奇数($22\ \mid\ 1=23$;$23\ \mid\ 1=23$;$-10\ \mid\ 1=-9$),若要让其变为偶数,把它 $\mid\ 1$后减一即可。
按位异或 ^
对于相同位,不同则有,相同则无。
即:相同位的两个数字不同则为 1;相同则为 0。
举例
1 | 1 ^ 1 = 0 |
则$5\wedge 28$为:
1 | 00101 // 5 |
作用
有趣的是,$\wedge$ 操作的逆运算是其本身,即两次异或同一个数后结果不变:$(a\wedge b)\wedge b=a$。因此,$\wedge$ 可用于简单加密:
若原文为 $123456789$,密钥为 $10086$,加密得密文:
1 | 123456789 ^ 10086 = 123464307 |
要解密,再次异或密钥即可:
1 | 123464307 ^ 10086 = 123456789 |
按位取反 ~
无则有,有则无。
即:把 1 换成 0,0 换成 1。
举例
1 | ~ 1 = 0 |
C++中取反运算实例:
1 |
|
输出 $65435$。
但若运行如下代码:
1 |
|
输出 $-101$。
这是因为有符号类型和无符号类型取反效果不同。
左移 <<
$a\ll b$ 把二进制下的 $a$ 后面添加 $b$ 个 0。
举例
1 | //(所有数字在十进制下表示) |
作用
看到例子,你发现了什么?
对!$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 | 4 >> 2 = 1 |
作用
和左移类似,$a\gg b$ 相当于 $\lfloor a\div 2^b\rfloor$(取整),因此可以用 $\gg 1$ 代替 $\div 2$。
位运算的应用
完~
本文作者:Xecades
本文链接:https://blog.xecades.xyz/drafts/BitwiseOperation.html
文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。
评论