跳到主要内容

位运算

多字节数据的存储​

多字节数据的地址是它在虚拟内存中序号最小的字节的地址；在绝大多数场合下，这些字节从最不重要到最重要的顺序排布。

数据的二进制表示​

  1. 用长度为 ww 的位向量 x⃗\vec x 来记录 ww 位的二进制表示
  2. 用 B2TwB2T_w 和 B2UwB2U_w 表示对二进制表示的解读
  3. 相反也可以用 U2BwU2B_w 和 T2BwT2B_w 将值转换为二进制表示
  4. 无符号和有符号值之间通过 U2TwU2T_w 和 T2UwT2U_w 转换
  5. TMinw,TMaxw,UMaxwTMin_w, TMax_w, UMax_w 表示几个特殊值
  6. +wt,+wu,∗wt,∗wu,−wt,−wu+^t_w, +^u_w, *^t_w, *^u_w, -^t_w,-^u_w是值之间的运算
B2Uw(x⃗)=∑i=0w−1xi2iB2U_w(\vec x)=\sum_{i=0}^{w-1}x_i2^i UMaxw=2w−1UMax_w=2^w-1 B2Tw(x⃗)=∑i=0w−2xi2i−xw−12w−1B2T_w(\vec x)=\sum_{i=0}^{w-2}x_i2^i-x_{w-1}2^{w-1} TMaxw=2w−1−1;TMinw=−2w−1TMax_w=2^{w-1}-1;\quad TMin_w=-2^{w-1} T2Uw(x)=B2Uw(T2Bw(x))={x+2wx<0xx≥0T2U_w(x)=B2U_w(T2B_w(x))=\begin{cases}x+2^w&x<0\\x&x\ge0\end{cases} U2Tw(u)={ux≤TMaxwu−2wu>TMaxwU2T_w(u)=\begin{cases}u&x\le TMax_w\\u-2^w&u>TMax_w\end{cases}

扩展与截断​

  1. 设 w′>ww'>w，则对无符号整数用 0 扩展使得 B2Uw(u⃗)=B2Uw′(u⃗′)B2U_w(\vec u)=B2U_{w'}(\vec u')
  2. 设 w′>ww'>w，则对有符号整数用最高位扩展使得 B2Tw(x⃗)=B2Tw′(x⃗′)B2T_w(\vec x)=B2T_{w'}(\vec x')
  3. 设 w′<ww'<w，则对无符号整数截断使得 u′=umod  2w′u'=u\mod 2^{w'}
  4. 设 w′<ww'<w，则对有符号整数截断使得 x′=U2Tw′(xmod  2w′)x'=U2T_{w'}(x\mod 2^{w'})

运算​

  1. s=x+wuy=(x+y)mod  2ws=x+^u_wy=(x+y)\mod 2^{w}，如果 s<xs<x（等价地，s<ys<y）则发生了上溢
  2. −wux=−xmod  2w-^u_wx=-x\mod 2^w
  3. s=x+wty=U2Tw((x+y)mod  2w)s=x+^t_wy=U2T_{w}((x+y)\mod 2^w)，如果 x,yx,y 符号相同但与 ss 符号不同则发生了上溢
  4. −wtx=U2Tw(−xmod  2w)-^t_wx=U2T_w(-x\mod 2^w)
  5. x∗wuy=xymod  2wx*^u_wy=xy\mod 2^w
  6. x∗wty=U2Tw(xymod  2w)x*^t_wy=U2T_w(xy\mod 2^w)
  7. 对无符号数 x，x << k 得到 x∗wu2kx*^u_w2^k
  8. 对有符号数 x，x << k 得到 x∗wu2kx*^u_w2^k
  9. 对无符号数 x，x >> k 得到 ⌊x/2k⌋\lfloor x/2^k\rfloor
  10. 对有符号数 x，x >> k 得到 ⌊x/2k⌋\lfloor x/2^k\rfloor，但 (x + (1 << k) - 1) >> k 得到 ⌈x/2k⌉\lceil x/2^k\rceil