位运算

原码、反码和补码

二进制有原码、反码和补码三种表示形式，在计算机内部使用补码来表示（即用补码存储）。

  • 原码：就是其二进制表示(注意，有一位符号位)
  • 反码：正数的反码就是原码，负数的反码是符号位不变，其余位取反（对应正数按位取反）。
  • 补码：正数的补码就是原码，负数的补码是 反码+1。
  • 符号位：最高位为符号位，0表示正数，1表示负数。在位运算中符号位也参与运算。
1
2
3
4
5
6
7
8
9
# int8 原码: 输出表示的二进制形式
3   -> 00 00 00 11
-3  -> 10 00 00 11
# 反码
3   -> 00 00 00 11
-3  -> 11 11 11 00
# 补码: 计算机内部实际存储的表示形式
3   -> 00 00 00 11
-3  -> 11 11 11 01
1
2
3
4
5
6
7
8
9
10
11
In [18]: bin(3)
Out[18]: '0b11'

In [19]: bin(-3)
Out[19]: '-0b11'
    
# 证明计算机内部存储是补码形式:
# &相当于and操作，如果采取的是原码形式存储计算，结果为: 3
# 如果采取的是补码形式存储计算，结果为: 1
In [21]: 3 & -3
Out[21]: 1

二进制操作

按位非(反)操作 ~

~会把数值的补码中的0和1全部取反(0变为1， 1变为0)，有符号整数的符号位在~运算中同样取反。

1
2
3
4
5
6
7
8
9
10
~ 1 = 0
~ 0 = 1
---------------------
00 00 01 01 => 5
~ =>
11 11 10 10 => -6
---------------------
11 11 10 11 => -5
~ =>
00 00 01 00 => 4

按位与操作 &

相当于and操作，只有两个对应位都为1时才为1。

1
2
3
4
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
1
2
3
4
5
00 00 01 01 => 5
&
00 00 01 10 => 6
---
00 00 01 00 => 4

按位或操作 |

相当于or操作，只有两个对应位中有一个为1时就为1。

1
2
3
4
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 1
1
2
3
4
5
00 00 01 01 => 5
|
00 00 01 10 => 6
---
00 00 01 11 => 7

按位异或操作 ^

只有两个对应位不同时才为1。

1
2
3
4
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
1
2
3
4
5
00 00 01 01 => 5
^
00 00 01 10 => 6
---
00 00 00 11 => 3

异或操作的性质

异或操作满足交换律和结合律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
A: 00 00 11 00
B: 00 00 01 11
C: 00 01 01 00
---
A^B: 00 00 10 11
B^A: 00 00 10 11
A^B = B^A
---
A^(B^C) = C^(B^A)
---
A^A: 00 00 00 00
0^A: 00 00 11 00
A^A = 0
0^A = A
---
A^B^A = A^A^B = 0^B = B

按左位移操作 <<

val << i将val的二进制表示向左移动i位所得的值。相当于val值乘以i次2。

1
2
3
4
00 00 10 11 => 11
11 << 3
---
01 01 10 00 => 88 = 11 * 2 * 2 * 2

按右位移操作 >>

val >> i将val的二进制表示向右移动i位所得的值。相当于val值除以i次2取整。

1
2
3
4
00 00 10 11 => 11
11 >> 2
---
00 00 00 10 => 2 = 11 / 2 / 2 / 2

在C#、C、Java中，/操作取得是整数

在Python中，/操作取得是浮点数， //操作取得才是整数

位运算案例

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

1
2
3
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

1.我们根据A^A = 0, 0^A = A来获取数组里不同得两个元素异或的结果：

1
2
3
4
1 => 00 00 00 01
2 => 00 00 00 10
3 => 00 00 00 11
5 => 00 00 01 01
1
2
3
1^2^1^3^2^5 = 1^1^2^2^3^5 = 3^5
=> 00 00 01 10
=> 6

2.我们取6的负数在内存中的补码表示：

1
11 11 10 10 => -6

3.对6和-6进行&操作

1
2
3
4
5
6
6 & -6 =>
00 00 01 10 
& 
11 11 10 10
---
00 00 00 10 => 2

经过&操作后保留了最后一个位置的1，前面我们知道，3^5=6，其中的二进制表示的最后一个位置的1意味着3和5在该位置的二进制位不相同，只有不相同异或后该位置才会变成1。

4.因此，我们对数组的元素进行分组，根据&操作分组，x&2 != 0为一组，x&2=0为另外一组：

1
2
3
4
5
1 & 2 = 0
5 & 2 = 0
---
3 & 2 = 2
2 & 2 = 2

最终将原数组分为：

1
2
[1, 1, 5]
[2, 2, 3]

5.分别对两组里元素进行异或操作即可得到不同的两个元素:

1
2
1 ^ 1 ^ 5 = 5
2 ^ 2 ^ 3 = 3