原码、反码、补码、负数、位运算

一些位运算符的基本使用,设计到内存中的数据结构,什么是原码、反码、补码,计算机如何表示负数,

1# 机器数

原码、反码和补码的设计是为了将符号位也加入 门电路 计算。

机器数中,八位二进制数只有后七位为真值的绝对值,第一位是正负符号。例如:

1
2
3
4
0000 0001 = +1
1000 0001 = -1
0111 1111 = 127
1111 1111 = -127

所以一个八位二进制数的取值范围是 +127 ~ -127,而并非 +255 ~ -255

正数的 反码 和原码相同
负数的 反码 符号位不变其余的按位取反

正数的 补码 和原码也相同
负数的 补码 则是其反码+1

补码补码 就是 原码

例如:

真值 原码 反码 补码 补码的反码 补码的补码
+1 0000 0001 0000 0001 0000 0001 0000 0001 0000 0001
+7 0000 0111 0000 0111 0000 0001 0000 0111 0000 0111
-1 1000 0001 1111 1110 1111 1111 1000 0000 1000 0001
-7 1000 1000 1111 0111 1111 1000 1000 0111 1000 1000

所以对于一个数,计算机都有三种编码方式,其中原码是人可以直接看懂的,而反码和补码(特别是负数的反码和补码)则是需要转换才能看懂的,是专门用来解决门电路设计问题的。

2# 减法计算

如果用 原码 计算 1 - 1,也就是 1 + -1:

1
2
3
真值      1     +    -1
原码 0000 0001 + 1000 0001 = 1000 0010
真值 = -2

明显计算是不成立的,而用 反码 计算:

1
2
3
4
5
真值      1     +    -1
原码 0000 0001 + 1000 0001
反码 0000 0001 + 1111 1110 = 1111 1111
原码 1000 0000
真值 = -0

-0 和 0 似乎一样含义,但对机器来说并不合理,并且同时会出现 1000 00000000 0000 两个源码编码表示同一个数 0,所以有了补码:

1
2
3
4
5
真值     1     +    -1
原码 0000 0001 + 1000 0001
补码 0000 0001 + 1111 1111 = 1 0000 0000 # 这里多出的一位为溢出位,舍弃
原码 0000 0000
真值 = 0

计算机内存中都是用补码进行计算的,内存中存放的都是补码。

3# 位运算

3.1# 位运算符

python 中有以下几种位运算:

1
2
3
4
5
6
7
8
符号  中文名  英文名        单双目   说明

& 位与 AND 双目 两位都为 1 时结果为 1,否则为 0
| 位或 OR 双目 两位都为 0 时结果为 0,否则为 1
^ 异或 XOR 双目 两位相同时为 0,两位相异时为 1
~ 取反 NOT 单目 1 变为 0,0 变为 1
<< 左移 LEFT-SHIFT 双目 各位左移 n 位,既乘以 2 的 n 次方
>> 右移 RIGHT-SHIFT 双目 各位右移 n 位,既除以 2 的 n 次方

3.1.1# 位运算的运算特征

位与、位或、异或 满足交换律、结合律、分配率。
对于交换律、结合律、分配率,这里 有一个特别有意思的图示说明。

交换律:

1
2
3
4
5
a * b = b * a

a & b = b & a
a | b = b | a
a ^ b = b ^ a

结合律:

1
2
3
4
5
a * b * c = a * ( b * c ) = ( a * b ) * c

a & b & c = a & ( b & c ) = ( a & b ) & c
a | b | c = a | ( b | c ) = ( a | b ) | c
a ^ b ^ c = a ^ ( b ^ c ) = ( a ^ b ) ^ c

分配率:

1
2
3
4
5
a * ( b + c ) = ( a * b ) + ( a * c )

a & ( b | c ) = ( a & b ) | ( a & c )
a ^ ( b & c ) = ( a ^ b ) & ( a ^ c )
......

3.2# & 位于运算

3.2.1# 定义

位与是双目运算符,两位都为 1 时结果才为 1。

1
2
3
4
5
6
7
8
9
10
真值:     7     &    13
补码: 0000 0111 & 0000 1101
位与: = 0000 0101
真值: 5

真值: 7 ^ -13
原码: 0000 0111 ^ 1000 1101
补码: 0000 0111 ^ 1111 0011
异或: = 0000 0011
真值: 3
1
print(7&13, 7&-13)
5 3

3.2.2# 位与的应用

使用位与求奇偶:

1
2
3
4
for i in range (5):
if i & 1:
continue
print(i)
0
2
4

3.2.3# 计算过程和理解

1
2
3
4
5
当 i 为 7 的时候:
0000 0111 & 0000 0001 = 0000 0001 = 真,所以 continue

当 i 为 8 的时候:
0000 1000 & 0000 0001 = 0000 0000 = 假,所以 print(i)

可知前面所有位和 1 做位与运算时结果都为 0(因为 1 的二进制形式为 0000 0001)。上述代码简单来说就是一个判断一个数的二进制形式末尾是否为1的判断式。

3.3# | 位或运算

位或是双目运算符,对应两位都为 0 时结果为 0,否则为 1。

1
2
3
4
真值:       3     |     6
补码: 0000 0011 | 0000 0110
位或: = 0000 0111
真值 7
1
print(3|6)
7

位或运算和布尔类型有类似的特性,而在各编译器中布尔类型通常占用远超过 1 bit,所以位或运算通常用来储存大量的布尔变量。

1
2
3
4
# 显示布尔类型占用空间大小
import sys
print(sys.version)
print(sys.getsizeof(True), sys.getsizeof(False))
3.5.3 (default, Sep 21 2018, 10:58:09) 
[GCC 4.2.1 Compatible Apple LLVM 10.0.0 (clang-1000.11.45.2)]
28 24

3.4# ~ 取反运算

3.4.1# 定义

取反是单目运算符,1 变为 0,0 变为 1。

1
2
3
4
5
6
7
8
9
10
11
12
真值             12
补码 0000 1100
按位取反 1111 0011 ;; 此时为内存中的值,需转原码,由补码的补码既是原码:
原码 1000 1101
真值 -13

真值 -127
原码 1111 1111
补码 1000 0001
按位取反 0111 1110 ;; 此时为内存中的值,需转原码,由补码的补码既是原码:
原码 0111 1110
真值 126

由此可见,因为 -0 的不存在,可以理解为任何数按位取反得到的值是 负的自己 - 1

3.4.2# 取反的应用

用取反取得一个数的绝对值:

1
2
3
4
def myabs(a):
return ~a + 1

print(myabs(15), myabs(-10))
-15 10

3.5# ^ 异或运算

3.5.1# 定义

异或是双目运算符,两位相同时为 0,两位相异为 1。

1
2
3
4
5
6
7
8
9
10
11
真值:    10     ^     9
补码: 0000 1010 ^ 0000 1001
异或: = 0000 0011
真值: 3

真值: 10 ^ -9
原码: 0000 1010 ^ 1000 1001
补码: 0000 1010 ^ 1111 0111
异或: = 1111 1101
原码: 1000 0011
真值: -3

异或运算是密码学核心运算之一,很多对称加密算法都是基于异或运算。

3.5.2# 异或的应用

使用异或交换两个数,不需要第三个数的做法:

1
2
3
4
5
6
7
8
def swap(a, b):
if a != b:
a = a ^ b
b = b ^ a
a = a ^ b
return a, b

print(swap(6, 13))
(13, 6)

3.5.3# 计算过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 第一行 a = a ^ b :
真值: a(6) ^ b(13)
补码: 0000 0110 ^ 0000 1101
异或: = 0000 1011
# 此时 a 的值为 0000 1011

# 第二行 b = b ^ a :
真值: b(13) ^ a
补码: 0000 1101 ^ 0000 1011
异或: = 0000 0110
# 此时 b 的值为 0000 0110

# 第三行 a = a ^ b :
真值: a b
补码: 0000 1011 ^ 0000 0110
异或: = 0000 1101
# 此时 a 的值为 0000 1101

# 计算结果:
a = 0b1101 = 13
b = 0b0110 = 6

3.5.4# 用数学进行理解

第一行:

1
a = a ^ b

因为任何数与自己异或结果为 0,任何数与 0 异或等于自己,且异或满足交换律,故将第一行带入第二行可以解读为:

1
b = b ^ ( a ^ b ) = b ^ b ^ a = a

这一步也就是把 a 的初始值赋给了 b

将第一行和第二行带入第三行可以解读为:

1
a = ( a ^ b ) ^ (b ^ ( a ^ b )) = ( a ^ a ) ^ ( b ^ b ) ^ b = 0 ^ 0 ^ b = b

这一步又把 b 的初始值赋给了 a。完成交换。

a = a ^ b 可以写为 a ^= b,所以函数还可以简写为:

1
2
3
4
5
6
7
8
def swap(a ,b):
if a != b:
a ^= b
b ^= a
a ^= b
return a, b

print(swap(6, 13))
(13, 6)

3.6# << 左移

3.6.1# 定义

将二进制数整体向左移动,高位舍弃,低位补零

1
2
3
4
真值:    10 << 2
补码: 0000 1010
左移: 0010 1000
真值: 40

简化一下负数的左移,假设是 16 位系统,过程如下:

1
2
3
4
5
6
真值:     -10 << 2
原码:1000 0000 0000 1010
补码:1111 1111 1111 0110
左移:1111 1111 1101 1000 # 高位舍弃
原码:1000 0000 0010 1000
真值: -40
1
print(10<<2, -10<<2)
40 -40

3.6.2# 左移的应用

在数字未溢出的情况下,左移可以用作计算一个数乘以 2 的 n 次方

1
2
3
4
def left_shift(x, n):
return x << n

print(left_shift(10, 2), left_shift(10, 5), left_shift(10, 1))
40 320 20

3.7# >> 右移

3.7.1# 定义

将二进制数整体向右移动,低位舍弃,高位补 符号位

1
2
3
4
5
6
7
8
9
真值:    24 >> 2
补码: 0001 1000
右移: 0000 0110
真值: 6

真值: 6 >> 2
补码: 0000 0110
右移: 0000 0001
真值: 1

负数的右移,还是用 16 位系统,过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
真值:     -24 >> 2
原码:1000 0000 0001 1000
补码:1111 1111 1110 1000
右移:1111 1111 1111 1010 # 高位舍弃
原码:1000 0000 0000 0110
真值: -6

真值: -6 >> 2
原码:1000 0000 0000 0110
补码:1111 1111 1111 1010
右移:1111 1111 1111 1110 # 高位舍弃
原码:1000 0000 0000 0010
真值: -2
1
2
print( 24 >> 2,  6 >> 2)
print(-24 >> 2, -6 >> 2)
6 1
-6 -2

3.7.2# 右移的应用

右移可以用作计算一个数 整除 2 的 n 次方,整除的方式类似于 \\

1
2
3
4
def right_shift(x, n):
return x >> n

print(right_shift(10, 2), right_shift(10, 5), right_shift(10, 1))
2 0 5

3.8# 位运算的性质

位运算有一些比较值得注意的性质,熟悉可提高构思逻辑时的效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
a | 0 = a
a & 1 = a
a & 0 = 0

a ^ a = 0
a ^ 0 =a

a | ~a = 1
a & ~a = 0
a & a = a
a | a = a

a | ( a & b ) = a
a & ( a | b ) = a
0%