整数与浮点数【详解】(二)
目录
1、截断
在逆元中，为什么 2 w 2^w 2
w
− x + x = 0 -x+x=0 −x+x=0？从循环队列看，是因为 2 ( w − 1 ) 2^{(w-1)} 2
(w−1)
-1+1又回到了起点，下面从位操作的观点理解这一点并认识到逆元确实也是一种模运算。（有关逆元的相关知识参考整数与浮点数【详解】（一））
如图1是 w w w位 U m a x + 1 U_{max}+1 U
max
+1的运算，可以看出产生了进位1，使位向量变成了 w + 1 w+1 w+1位。但 w + 1 w+1 w+1位并不符合一个 w w w位的无符号数，因此机器将溢出的这一位进位1进行截断，得到了全0的位向量即数字0。那么截断的本质是如何？考察一个 w w w位无符号数，将其截断为 k k k位，即：
B 2 U w ( x ⃗ ) = ∑ i = 0 w − 1 2 i x i → B 2 U k ( x ⃗ ) = ∑ i = 0 k − 1 2 i x i B2U_w (x ⃗ ) = \sum_{i=0}^{w-1}{2^i}x_i→B2U_k (x ⃗ ) = \sum_{i=0}^{k-1}{2^i}x_i
B2U
w
(x⃗)=
i=0
∑
w−1
2
i
x
i
→B2U
k
(x⃗)=
i=0
∑
k−1
2
i
x
i
注意到对任何 i ≥ k , 2 i m o d 2 k = 0 i≥k,2^i mod 2^k=0 i≥k,2
i
mod2
k
=0，所以上式实际上是：
B 2 U k ( x ⃗ ) = ∑ i = 0 k − 1 2 i x i = ∑ i = 0 w − 1 2 i x i m o d 2 k = B 2 U w ( x ⃗ ) m o d 2 k B2U_k (x ⃗ ) = \sum_{i=0}^{k-1}{2^i}x_i= \sum_{i=0}^{w-1}{2^i}x_i mod2^k=B2U_w (x ⃗ )mod2^k
B2U
k
(x⃗)=
i=0
∑
k−1
2
i
x
i
=
i=0
∑
w−1
2
i
x
i
mod2
k
=B2U
w
(x⃗)mod2
k
可以说，截断的本质就是模运算，通过模运算把高于k位的所有数字置0，那么逆元的本质就体现在整数的模运算：
无符号数的截断定义为：
假设一个 w w w位位向量 x ⃗ = [ x ( w − 1 ) , x ( w − 2 ) , … … x 0 ] x ⃗=[x_{(w-1)},x_{(w-2)},……x_0] x⃗=[x
(w−1)
,x
(w−2)
,……x
0
]，将其截断为 k k k位位向量，则：
x ′ = x m o d 2 k x'=x mod 2^k
x
′
=xmod2
k
其中 x x x， x x x’分别为截断前后位向量对应的无符号数
有符号数的截断比无符号数多一步Set Sign，如图3，其本质与无符号数相同，但需要把截断后的数设置一个负权表示有符号
有符号数的截断定义为：
假设一个 w w w位位向量 x ⃗ = [ x ( w − 1 ) , x ( w − 2 ) , … … x 0 ] x ⃗=[x_{(w-1)},x_{(w-2)},……x_0] x⃗=[x
(w−1)
,x
(w−2)
,……x
0
]，将其截断为 k k k位位向量，则：
x ′ = U 2 T ( x m o d 2 k ) x'=U2T(x mod 2^k)
x
′
=U2T(xmod2
k
)
其中x’为截断后位向量对应的有符号数，x实际意义上是截断前的有符号数，但在截断时把它视为无符号数进行截断便于模运算且并不影响结果，换言之，有符号数的截断就是把有符号数看成无符号数截断后再转为有符号数
2、无符号数与有符号数之间的转换
无符号数与有符号数间的区别仅在最高位权的正负，因此两者的转换也就是一位权值的变化，这个变化并不影响位向量本身。若最高位是1，那么转换前后会相差一个 2 w − 1 2^{w-1} 2
w−1
；若最高位是0，那么转换前后不变。
值得注意，执行一个运算的运算数若一个有符号而一个无符号，则C语言会隐式地将有符号数强制类型转换为无符号数
3、位扩展
与截断相对应，当一个 w w w位位向量 x ⃗ = [ x ( w − 1 ) , x ( w − 2 ) , … … x 0 ] x ⃗=[x_{(w-1)},x_{(w-2)},……x_0] x⃗=[x
(w−1)
,x
(w−2)
,……x
0
]要转变为一个 w ′ w' w
′
位的位向量，就会在多出 w ′ − w w'-w w
′
−w个的高位，这些高位的填充就是位扩展考虑的问题。
无符号数的位扩展是0扩展，有符号数的位扩展是符号扩展不同数据大小间数据的转换，以及无符号数、有符号数间的转换会影响程序行为，甚至导致意想不到的结果。例如：
short sx =-12345 /*bitMode=0xCFC7*/ unsigned uy=sx /*bitMode=0xFFFFCFC7 uy=4294954951*/
结果表明这里类型转换是先位扩展为int32，再转为unsigned。由于sx符号位为1，有符号数位扩展使高位全为1，此时再转为无符号数相当于-12345加上了232，得到4294954951
在这个例子中还需要指出一点：符号扩展不影响真值。
从0xCFC7→0xFFFFCFC7似乎改变了数值，其实从理论上考虑并没有产生影响：
B 2 U w ( x ⃗ ) = − x w − 1 2 w − 1 + ∑ i = 0 w − 2 2 i x i B2U_w (x ⃗ ) =-x_{w-1}2^{w-1} +\sum_{i=0}^{w-2}{2^i}x_i
B2U
w
(x⃗)=−x
w−1
2
w−1
+
i=0
∑
w−2
2
i
x
i
将这个有符号数向左扩展一位，得到
B 2 U w + 1 ( x ⃗ ) = − x w 2 w + x w − 1 2 w − 1 + ∑ i = 0 w − 2 2 i x i B2U_{w+1} (x ⃗ ) =-x_{w}2^{w} +x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}{2^i}x_i
B2U
w+1
(x⃗)=−x
w
2
w
+x
w−1
2
w−1
+
i=0
∑
w−2
2
i
x
i
当 x w − 1 x_{w-1} x
w−1
=0时显然有 B 2 T w ( x ⃗ ) = B 2 T w + 1 ( x ⃗ ) B2T_w (x ⃗ )= B2T_{w+1} (x ⃗ ) B2T
w
(x⃗)=B2T
w+1
(x⃗)；当 x w − 1 = 1 x_{w-1}=1 x
w−1
=1时， − 2 w + 2 w − 1 = − 2 w − 1 = − x w − 1 2 w − 1 -2^w+2^{w-1}=-2^{w-1}=-x_{w-1} 2^{w-1} −2
w
+2
w−1
=−2
w−1
=−x
w−1
2
w−1
，即仍然有 B 2 T w ( x ⃗ ) = B 2 T w + 1 ( x ⃗ ) B2T_w (x ⃗ )= B2T_{w+1} (x ⃗ ) B2T
w
(x⃗)=B2T
w+1
(x⃗)。进一步由归纳法得到符号扩展不影响真值。
