位运算的操作

算法

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

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

含义运算符举例英文表示
按位与$a$ & $b$$and$
按位或$a\mid b$$or$
按位异或$a$ ^ $b$$xor$
按位取反~ $a$$not$
左移$a$ << $b$$shl$
右移(带符号)$a$ >> $b$$shr$

按位与&

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

即:相同位的两个数字同为1,则为1;有一个不为1,则为0.

举例

1
2
3
1 & 1 = 1
1 & 0 = 0
0 & 0 = 0

则$5\space and\space 28$为:

1
2
3
4
  00101    //5
& 11100 //28
-------
00100 //4

即$5\space and\space 28\space =\space 4$

作用

$and$运算常用于二进制的取位操作,可以判断整数的奇偶性(二进制末尾是0为偶数,是1为奇数). 一个数 $and$ $1$就取二进制下的最后一位.


按位或|

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

即:相同位的两个数字只要有一个为1,则为1;否则为0.

举例

1
2
3
1 | 1 = 1
1 | 0 = 1
0 | 0 = 0

则$5\space or\space 28$为:

1
2
3
4
  00101    //5
| 11100 //28
-------
11101 //29

作用

$or$运算常用于二进制下的赋值,一个数 $or$ $1$把二进制末尾的数变成1,即把这个数变成大于或等于原数的最小奇数($22$ | $1$ $=$ $23$ ; $23$ | $1$ $=$ $23$ ; $-10$ | $1$ $=$ $-9$),若要让其变为偶数,把它 $or$ $1$后减一即可.


按位异或^

对于相同位,不同则有,相同则无.

即:相同位的两个数字不同则为1;相同则为0.

举例

1
2
3
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0

则$5\space xor\space 28$为:

1
2
3
4
  00101    //5
^ 11100 //28
-------
11001 //25

作用

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

若原文为$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
#include<iostream>
using namespace std;
int main()
{
unsigned short a=100;
a=~a;
cout<<a;
return 0;
}

输出$65435$
但若运行如下代码:
1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main()
{
unsigned short a=100;
cout<<~a;
return 0;
}

输出$-101$
即有符号类型和无符号类型取反效果不同.


左移<<

$a$ << $b$把二进制下的$a$后面添加$b$个0.

举例

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

作用

看到例子,你发现了什么?

对!$a$ << $n = a\times 2^n$,要计算$2^n$,可以不用$pow()$,用左移运算$(1$ << $n)$,要快得多. 定义常量也可以用左移运算:$1$ << $16$ $-$ $1$可以表示$65535$.


右移>>

$a$ >> $b$把二进制下的$a$向右移$b$位,低位舍去,高位补0.

举例

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

作用

和左移类似,$a$ >> $b$相当于$\lfloor a\div 2^b\rfloor$(取整),因此可以用>> $1$代替$\div 2$


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

完~

本文作者:Xecades

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

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

评论