作为在互联网领域工作的程序员啊,我们需要不断地学习。自己也坚持每天刷一两个 LeetCode 题目,在刷题的过程中,发现有不少题目都涉及到一些位运算的知识,这篇文章记录一下。
- 介绍
- 运算
- 按位与(&)
- 按位或(|)
- 按位异或(^)
- 左移(<<)
- 右移(>>)
- 取反(~)
介绍
位运算是把数字用二进制表示之后,对每一位上 0 或 1 的运算。
运算
接下来我们举一个例子一个个运用下方的运算符。
按位与(&)
将参与运算的两个数字,换算为二进制进行运算。只有当相应位上的数都是 1 时,该位取 1,否则取 0。
将数字 3 与 2 进行按位于运算
1 1 3的二进制
1 0 2的二进制
————
1 0 结果的二进制,对应十进制数字为 2
所以:3 & 2 = 3
复制代码
按位或(|)
将参与运算的两个数字,换算为二进制进行运算。只要相应位上数是有 1 时,该位取 1,否则取 0。
将数字 3 与 2 进行按位或运算
1 1 3的二进制
1 0 2的二进制
----
1 1 结果的二进制,对应十进制数字为 3
所以:3 | 2 = 3
复制代码
按位异或(^)
将参与运算的两个数字,换算为二进制进行运算。只要相应位上数不相同时,该位取 1,否则取 0。
将数字 3 与 2 进行按位异或运算
1 1 3的二进制
1 0 2的二进制
----
0 1 结果的二进制,对应十进制数字为 1
所以:3 ^ 2 = 1
复制代码
左移(<<)
将参与运算的两个数字,换算为二进制进行运算。将二进制位全部向左移动若干位,后续位置补 0 。
将数字 3 左移 2 位
1 1 3的二进制
1 1 0 0 左移两位。结果的二进制,对应十进制数字为 12
所以:3 << 2 = 12
复制代码
右移(>>)
将参与运算的两个数字,换算为二进制进行运算。将二进制位全部向右移动若干位,前面空出的位置补 0,后续移出的数字移除。
将数字 3 右移 2 位
1 1 3的二进制
0 0 1 1
0 0 结果的二进制。右移两位,移出去的 1 移除。对应十进制数字为 0
所以:3 >> 2 = 0
复制代码
右移运算可用来代替除法,且效率会比除法更高。
利用右移运算代替除法。
将数字 3 右移 1 位。
1 1 3的二进制
0 1 1
0 1 结果的二进制。右移两位,移出去的 1 移除。对应十进制数字为 1
所以:3 >> 1 = 1
复制代码
取反(~)
首先,我们需要知道计算机内部在做数学运算时,都是以补码为标准的。
关于原码、反码及补码的只是这里不多做介绍了。 这篇文章对这三个码进行了一些基本介绍。
这里我们说一些结论:
- 正数的原码、反码及补码都一样。
- 负数的原码最高位为 1 开头,反码是最高符号位不变,其余位在原码的基础上取反,补码在反码的基础上 +1 即可得到。
取反操作
将参与运算的两个数字,换算为二进制进行运算。每个位置上都取相反值,1 变成 0,0 变为 1。
例子1:对正数进行取反
对数字 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:对负数进行取反
对数字 -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
复制代码