Integer Arithmetic
Integer Arithmetic(整数运算)
Unsigned
Addition
For x and y $0 \leq x \leq 2^w$ , $0 \leq y \leq 2^w$
$$ x+_{w}^{u}y= \begin{cases} x+y, & \text {x + y < $2^w$} \\ 3n+1, & \text{$2^{w}\leq{x+y}{\leq}2^{w+1}$} \end{cases} $$
Inverse
For x,$0 \leq x \leq 2^w$
$$ x + x^{'} = x^{'} + x = 0 $$
$$ y - x => y + x^{'} $$
For $x, x^{'} => 0 \leq x \leq 2^{w}, 0 \leq x^{'} < 2^{w}$
$$ x + x^{'} = 2^{w} = 0 $$
$$ -_{w}^{u}y= \begin{cases} x, & \text {x = 0} \\ 2^{w}-x, & \text{x $\geq$ 0} \end{cases} $$
Multiplication
x | $x_{w-1},x_{w-2}…x_{0}$ |
---|---|
y | $y_{w-1},y_{w-2}…y_{0}$ |
$z=x{\cdot}y$ | $\underbrace{Z_{w-1},Z_{w-2}…Z_0}_{w}$ |
$$ x *_{w}^{u}y= (x{\cdot}y) mod 2^w $$
Two’s Complement
Addition
For x and y $-2^{w-1}{\leq}{x}{\leq}2^{w-1}-1, -2^{w-1}{\leq}{y}{\leq}2^{w-1}-1$
$$ x+_{w}^{t}y= \begin{cases} x+y-2^{w}, & \text {$2^{w-1}{\leq}{x+y}$(Positive overflow)} \\ x+y, & \text{$-2^{w-1}\leq{x+y}{<}2^{w-1}$} \\ x+y+2^{w}, & \text{x+y<$-2^{w-1}$(Negative overflow)} \end{cases} $$
Code
|
|
Negation
For x $-2^{w-1}{\leq}x<2^{w-1}-1$
$$ -{w}^{t}x= \begin{cases} -x, & \text {$x > TMin_w$} \\ TMin{w}, & \text{$x=TMin_{w}$} \end{cases} $$
$$ |Tmin_x| = |Tmax_w| +1 $$
$$ Tmin_w + Tmin_w = -2^{w-1}+(-2^{w-1})=-2^{w} $$
$$ Tmin_w+_{w}^{t}Tmain_w = -2^w+2^w=0 $$
Multiplication
$$ x *_{w}^{t}y=U2T_w((x{\cdot}y)\mod{2^w}) $$
Three-bit Multiplication Example
Mode | x | y | ${x}{\cdot}{y}$ | Truncated ${x}{\cdot}{y}$ |
---|---|---|---|---|
Unsigned | $5[101]$ | $3[011]$ | $15[001 111]$ | $7[111]$ |
Two’s Complement | $-3[101]$ | $3[011]$ | $-9[110 111]$ | $-1[111]$ |
Unsigned | $4[100]$ | $7[111]$ | $28[001 100]$ | $4[100]$ |
Two’s Complement | $-4[100]$ | $-1[111]$ | $4[000 100]$ | $-4[100]$ |
Unsigned | $3[011]$ | $3[011]$ | $9[001 001]$ | $1[001]$ |
Two’s Complement | $3[011]$ | $3[011]$ | $9[001 001]$ | $1[001]$ |
For signed integer x, y and unsigned integer $x^{'}, y^{'}$
$$ B2U_w(x^{'})=x_{w-1}{\cdot}2^{w-1}+x_{w-2}{\cdot}2^{w-2}+…+x_{0}{\cdot}2^{0} \\ B2T_w(x)=x_{w-1}{\cdot}-2^{w-1}+x_{w-2}{\cdot}2^{w-2}+…+x_{0}{\cdot}2^{0} \\ B2U_w(x^{'})-B2T_w(x)=x^{w-1}{\cdot}2^{w} \\ x^{'} = x + x_{w-1}{\cdot}2^{w} \\ y^{'}=y+{y_{w-1}}{\cdot}2^w \\ ({x^{'}}{\cdot}{y^{'}})\mod{2^w} = [(x+x_{w-1}{\cdot}{2^w}){\cdot}(y+{y_{w-1}}{\cdot}{2^w})] \mod 2^w \\ ({x^{'}}{\cdot}{y^{'}})\mod{2^w} = [x{\cdot}y+(x_{w-1}y+y_{w-1}x)2^w]+x_{w-1}y_{w-1}2^{2w}] \mod 2^w \\ ({x^{'}}{\cdot}{y^{'}})\mod{2^w} = (x{\cdot}y\mod2^w) $$
Multiplying by Constants
$x{\cdot}2$ | $x«1$ |
---|---|
$x{\cdot}4$ | $x«2$ |
… | … |
$x{\cdot}2^{k}$ | $x«k$ |
For unsigned integer x
$$ x_{w-1}|x_{w-2}|…|x_0 \\ B2U_w(x)=x_{w-1}{\cdot}2^{w-1}+x_{w-2}{\cdot}2^{w-2}+…+x_0{\cdot}2^0=\sum_{i=0}^{w-1}x_{i}2^{i} \\ x_{w-1}|x_{w-2}|…|x_0|\underbrace{0|…|0}_{k} \\ $$
$$ B2U_{w+k}(x^{'})=x_{w-1}{\cdot}2^{w-1+k}+x_{w-2}{\cdot}2^{w-2+k}+…+x_0{\cdot}2^k+0{\cdot}2^{k-1}+0{\cdot}2^{k-2}+…+0{\cdot}2^{0} \\ B2U_{w+k}(x^{'})=\sum_{i=0}^{w-1}x_{i}2^{i}{\cdot}2^k=x2^k $$
Example
$x * 14$
0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
---|
$$ 14 = 2^3+2^2+2^1 \\ x{\cdot}14=x{\cdot}(2^3+2^2+2^1)=(x«3)+(x«2)+(x«1) \\ x{\cdot}14=x{\cdot}(2^4-2^1)=(x«4)+(x«1) $$
Dividing by Powers of 2
$k$ | $»k(binary)$ | $Decimal$ | $12340/2^k$ |
---|---|---|---|
0 | 0011000000110100 | 12340 | 12340.0 |
1 | 0001100000011010 | 6170 | 6170.0 |
4 | 0000001100000011 | 771 | 771.25 |
8 | 0000000000110000 | 48 | 48.203125 |
0 | 1100111111001100 | -12340 | -12340 |
1 | 1110011111100110 | -6170 | -6170.0 |
4 | 1111110011111100 | -772 | -771.25 |
8 | 1111111111001111 | -49 | -48.203125 |
For unsigned integer x
$x$ | $x_{w-1}$ | $x_{w-2}$ | $…$ | $x_{k}$ | $x_{k-1}$ | $…$ | $x_{0}$ | |||
$x»k$ | 0 | $…$ | 0 | $x_{w-1}$ | $x_{w-2}$ | $…$ | $x_k$ | |||
index | $k$ | … | 0 | $w-k$ | $w-k-1$ | … | 0 | |||
$x_1$ | $x_{w-1}$ | $x_{w-2}$ | $…$ | $x_k$ | ||||||
index | $w-k$ | $w-k-1$ | 0 | |||||||
$x_2$ | $x_{k-1}$ | $…$ | $x_{0}$ | |||||||
$x_1{\cdot}2^k$ | $x_{w-1}$ | $x_{w-2}$ | $…$ | $x_k$ | 0 | $…$ | 0 | |||
index | $w-k$ | $w-k-1$ | … | 0 | k | … | 0 | |||
$x_1{\cdot}2^k+x_2$ | $x_{w-1}$ | $x_{w-2}$ | $…$ | $x_{k}$ | $x_{k-1}$ | $…$ | $x_{0}$ | |||
$w-k$ | $w-k-1$ | … | 0 | $k$ | … | 0 |
$$ 0 \leq x_2 \leq 2^k \\ \lfloor{x_2/w^k}\rfloor = 0 \\ \lfloor{x_2/w^k}\rfloor=\lfloor{(x_1[\cdot]2^k+x_2)}\rfloor = x_1 $$
资料由
九曲阑干
视频提供,如有侵权,联系sliver_horn@qq.com
删!