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

1
2
3
4
5
6
7
8
9

#include <stdio.h>

int main() {
    char x = 127;
    char y = 1;
    char z = x + y;
    printf("z=%d",z);
    return 0;
}

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 删！