位运算记录

Posted on In

作为在互联网领域工作的程序员啊，我们需要不断地学习。自己也坚持每天刷一两个 LeetCode 题目，在刷题的过程中，发现有不少题目都涉及到一些位运算的知识，这篇文章记录一下。

  • 介绍
  • 运算
    • 按位与(&)
    • 按位或(|)
    • 按位异或(^)
    • 左移(<<)
    • 右移(>>)
    • 取反(~)

介绍

位运算是把数字用二进制表示之后，对每一位上 0 或 1 的运算。

运算

接下来我们举一个例子一个个运用下方的运算符。

按位与(&)

将参与运算的两个数字，换算为二进制进行运算。只有当相应位上的数都是 1 时，该位取 1，否则取 0。

1
2
3
4
5
6
7
8
将数字 3 与 2 进行按位于运算

1 1		3的二进制
1 0		2的二进制  
————
1 0		结果的二进制，对应十进制数字为 2

所以：3 & 2 = 3

按位或(|)

将参与运算的两个数字，换算为二进制进行运算。只要相应位上数是有 1 时，该位取 1，否则取 0。

1
2
3
4
5
6
7
8
将数字 3 与 2 进行按位或运算

1 1		3的二进制
1 0		2的二进制  
----
1 1		结果的二进制，对应十进制数字为 3    

所以：3 | 2 = 3

按位异或(^)

将参与运算的两个数字，换算为二进制进行运算。只要相应位上数不相同时，该位取 1，否则取 0。

1
2
3
4
5
6
7
8
将数字 3 与 2 进行按位异或运算

1 1		3的二进制
1 0		2的二进制  
----
0 1		结果的二进制，对应十进制数字为 1

所以：3 ^ 2 = 1

左移(<<)

将参与运算的两个数字，换算为二进制进行运算。将二进制位全部向左移动若干位，后续位置补 0 。

1
2
3
4
5
6
将数字 3 左移 2 位

1 1			3的二进制
1 1 0 0		左移两位。结果的二进制，对应十进制数字为 12

所以：3 << 2 = 12

右移(>>)

将参与运算的两个数字，换算为二进制进行运算。将二进制位全部向右移动若干位，前面空出的位置补 0，后续移出的数字移除。

1
2
3
4
5
6
7
将数字 3 右移 2 位

1 1			3的二进制
0 0 1 1		
0 0			结果的二进制。右移两位，移出去的 1 移除。对应十进制数字为 0

所以：3 >> 2 = 0

右移运算可用来代替除法，且效率会比除法更高。

1
2
3
4
5
6
7
8
利用右移运算代替除法。
将数字 3 右移 1 位。

1 1			3的二进制
0 1 1		
0 1			结果的二进制。右移两位，移出去的 1 移除。对应十进制数字为 1

所以：3 >> 1 = 1

取反(~)

首先，我们需要知道计算机内部在做数学运算时，都是以补码为标准的。

关于原码、反码及补码的只是这里不多做介绍了。
这篇文章对这三个码进行了一些基本介绍。

这里我们说一些结论：

  • 正数的原码、反码及补码都一样。
  • 负数的原码最高位为 1 开头，反码是最高符号位不变，其余位在原码的基础上取反，补码在反码的基础上 +1 即可得到。

取反操作

将参与运算的两个数字，换算为二进制进行运算。每个位置上都取相反值，1 变成 0，0 变为 1。

例子1：对正数进行取反

1
2
3
4
5
6
7
8
9
10
11
对数字 3 进行取反。这里就利用 8 位来存储二进制数值。

0 0 0 0 0 0 1 1		3的二进制原码

1 1 1 1 1 1 0 0		取反之后得到结果的原码，我们需要转化为补码供计算机计算

1 0 0 0 0 0 1 1		根据原码得到结果的反码

1 0 0 0 0 1 0 0		上面反码基础上 +1 得到补码，其十进制值为 -4

所以：~3 = -4

例子2：对负数进行取反

1
2
3
4
5
6
7
8
9
10
11
12
对数字 -4 进行取反。这里就利用 8 位来存储二进制数值。
其实只是将正数的过程反过来就好。

1 0 0 0 0 1 0 0		-4的二进制补码

1 0 0 0 0 0 1 1		在补码的基础上 -1 得到反码

1 1 1 1 1 1 0 0		根据反码得到其原码

0 0 0 0 0 0 1 1		每位取反之后得到结果的原码。结果的十进制为 3

所以：~(-4) = 3