§2.0 Extend Vector Integer Represent

其他进制视作Vetor表示法

我们将表示和代表的数字分离, EveryThing Base on Dec

数的十进制表示我们也称 “数本身” , 所有数的表示我们都默认以十进制表示

数的其他进制表示我们视作向量  x⃗=[xw1,xw−2...x0]\vec{x} = [x_{w_1},x_{w-2}...x_0]x=[xw1​​,xw−2​...x0​]﻿ 的一种缩写

我们接下来研究数的进制

快捷记忆: 基数为2的等比数列求和需要记忆

20+21…2i=2i+1−12^0 +2^1 \dots 2^i = 2^{i+1} -120+21…2i=2i+1−1﻿

Unsigned Encoding 无符号数编码

则有 Binay Codeing to Number using Unsigned Decoding  函数 

B2U_w(\vec {x}) \doteq x_{w-1}2^{w-1} +x_{w-2}2^{w-2} \dots x_{0}2^{0} \\ =\sum\limits_{i=0}^{w-1} x_i2^i

范围

 max=∑i=0w−12i=a1(1−qn)1−q max=\sum\limits_{i=0}^{w-1} 2^i = \frac{ a_1(1-q^n) } {1-q}
max=i=0∑w−1​2i=1−qa1​(1−qn)​﻿

=2w−1+1−1=2w−1= 2^{w-1+1} -1 = 2^{w} -1=2w−1+1−1=2w−1﻿

Two’s-Complement Signed Encoding有符号数

采用补码(two’s-complement)编码形式
即 Binay Codeing to Number using Complement Decoding

B2T_w(\vec {x}) \doteq -x_{w-1}2^{w-1} +x_{w-2}2^{w-2} \dots x_{0}2^{0}

范围

max=20+21…2w−2=2w−1−1max =2^0 +2^1 \dots 2^{w-2} = 2^{w-1} -1max=20+21…2w−2=2w−1−1﻿ 

min=−2w−1min = -2^{w-1}min=−2w−1﻿

x⃗\vec x x﻿ 相当于 二进制编码 所对应的 向量串

2T2T2T﻿ 相当于, 用补码规则转换到正常数

Relate Opreate

Shift Operation in C

左移: C语言中都是指逻辑左移, 均补0

逻辑右移: 统一补0

算数右移: 根据符号位决定补1还是补0

C语言中, 虽然没有明确规定有符号数使用哪种右移几

但是几乎所有的编译器都是对有符号使用算数右移, 无符号逻辑右移

Transfer Rule

小类型 → 大类型: 

对于Signed , 高位根据符号位1或0 扩展

证明: 比较B2TwB2T_wB2Tw​﻿ 和 B2Tw+1B2T_{w+1}B2Tw+1​﻿ 做差

大类型 → 小类型

对于Unsigned , 截断高位保留低位 ,等效取模运算 

对于Signed: 等价于先视作无符数截断,使用 B2UwB2U_wB2Uw​﻿ 之后再使用U2TwU2T_wU2Tw​﻿ 转换

Implicit Transfer

Exmaple Code

int a = -1;
unsigned int b = 0;

if(a<b)
	printf("-1<0");
if(a>b)
	printf("-1>0");

Copy

C++

C语言会隐式的把有符号转换成无符号表示

Transfer Funtion

对于同样的Binary Code , 不同Decoding 结果差

B2Uw(x⃗)−B2Tw(x⃗)=2∗xw−12w−1=xw−12wB2U_w(\vec {x}) - B2T_w(\vec {x}) = 2 * x_{w-1} 2^{w-1} = x_{w-1} 2^wB2Uw​(x)−B2Tw​(x)=2∗xw−1​2w−1=xw−1​2w﻿ 

上述的结果是用Binary Code的信息作为参数表述

如果使用Decoding 后的结果, 来表示转换的话则有

T2Uw(x⃗) and U2Tw(x⃗)T2U_w(\vec x)\ and \ U2T_w(\vec x)T2Uw​(x) and U2Tw​(x)﻿ 

T2U U2T

\begin{equation} T2U_w(x)=\left\{ \begin{aligned} x+2^w & , & x<0 \\ x & , & x\geq0 \end{aligned} \right. \end{equation} \\ ~\\ \begin{equation} U2T_w(x)=\left\{ \begin{aligned} x & , & x<2^{w-1} \\ x-2^w & , & x\geq2^{w-1} \end{aligned} \right. \end{equation}

对于同样的二进制表示Vector, 
已经转换成一种编码方式, 切换成另一种编码方式, 所带来的数的差异

Interger Arithmetic

无符号加法

无符号加法定义

x+_w^uy \\ \text{ if: } x+y<2^w \implies x+_w^uy:=x+y \\ \text{ if: } x+y\geq 2^w \implies x+_w^uy:=x+y -2^w

我们称 x+y≥2wx+y\geq 2^wx+y≥2w﻿ 所对应的情况为溢出

表示: 我们记作 +wu+_w^u +wu​﻿ 以避免重载带来的歧义
上标 uuu﻿ 表示无符号数, 下标 www﻿ 表示编码位数

无符号判定溢出

方法: 

如果发生了溢出, 我们有溢出结果 zzz﻿ 小于原来两个数中任何一个数

证明

若有 z=x+y−2w<x  ⟺  x+y<x+2w  ⟺  y<2wz = x+y - 2^w <x\\

\iff x+y < x+2^w \\

\iff y<2^w z=x+y−2w<x⟺x+y<x+2w⟺y<2w﻿

  最后一个条件显然成立, 故原命题成立

代码实现: return x+y>x 1为无溢出, 0为溢出

有符号加法

有符号加法定义

x+_w^ty \\ \text{ if: } -2^{w-1} \leq x+y<2^{w-1} \implies x+_w^ty:=x+y \\ ~\\\text{ if: } x+y\geq 2^{w-1} \implies x+_w^uy:=x+y -2^w \\ \text{ if: } x+y< -2^{w-1} \implies x+_w^uy:=x+y +2^w

我们表示成: +ws+_w^s+ws​﻿ , 其中 ttt﻿ 代表互补

注意: 溢出后, 我们还是增减2w2^w2w﻿ 而不是增减 2w−12^{w-1}2w−1﻿ 

溢出判断

当两个正数相加 , 得到负数, 代表正溢出

当两个负数相加 , 得到正数, 代表负溢出

无符号减法

何为逆元: 满足x+x’=0x+x’ =0x+x’=0﻿ 即可

对于无符号数正数而言,通过正溢出: x+x’=2w=0x+x’ = 2^w =0x+x’=2w=0﻿ 

 固有如下运算定义 −wu-_w^u−wu​﻿

\begin{equation} -_u^w(x)=\left\{ \begin{aligned} 0 & , & x=0 \\ 2^w-x & , & x\geq0 \end{aligned} \right. \end{equation} \\

有符号减法

固有如下运算定义 −wt-_w^t−wt​﻿

\forall x , 2^{w-1} \leq x<2^{w-1}\\ \begin{equation} -_w^t(x)=\left\{ \begin{aligned} -x & , & Other\ Condition\\ TMin_w & , & x=TMin_w \end{aligned} \right. \end{equation} \\

x=TMinw=−2w−1x = TMin_w= -2^{w-1}x=TMinw​=−2w−1﻿ 分析

由于补码正数负数的范围非对称, 其最小值 −2w−1-2^{w-1}−2w−1﻿ 无直接对应的正数逆元

故我们需要通过负溢出计算出在这个范围下的逆元

则有 x+y+2w=0x+y+2^w =0 x+y+2w=0﻿ 确定触发负溢出条件 , 解得TMinwTMin_wTMinw​﻿的逆元为本身

无符号乘法

z=(x∙y)mod 2wz=(x\bullet y) mod \ 2^w z=(x∙y)mod 2w﻿ 

不截取的时候, z应该为 2w2w2w﻿ 位, 我们取余相当于截取