苏州建设工程公司网站建立自己的摄影网站

当前位置： 首页 > news >正文

苏州建设工程公司网站,建立自己的摄影网站,网站建设数字的代码编写,东城企业网站开发文章目录无符号加法练习1练习2补码加法练习1练习2练习3练习4补码的非练习无符号乘法补码乘法练习1练习2练习3乘以常数练习1练习2除以2的幂练习1练习2关于整数运算的最后思考练习无符号加法 考虑两个非负整数x和y#xff0c;满足0≤x,y2w0 \le x, y 2^w0≤x,y2w满足0≤x,y2w0 \le x, y 2^w0≤x,y2w每个数都能表示为一个w位的无符号数。如果要计算xy其结果的可能取值范围是0≤xy≤2w1−20 \le xy \le 2^{w1}-20≤xy≤2w1−2表示该值可能需要w1位。如果xy的结果又要和别的数做加法那可能需要更多的位表示运算结果。这种字长膨胀意味着要想完整地表示运算的结果我们不能对整型长度做任何限制。 但实际情况是在C语言中整型变量占固定大小的字节和位当整数运算结果超出了整型变量的表示范围时计算机运算的结果是截断后的值与预期值有偏差。 我们定义操作wu^u_wwu​是w位的无符号加法。 原理无符号数加法。 对满足0≤x,y2w0 \le x,y2^w0≤x,y2w的xxx和yyy有 xwuy{xy,0≤xy≤2w−1xy−2w,2w≤xy≤2w1−2\begin{align} x^u_wy \begin{cases} xy,\quad 0 \le xy \le 2^w -1 \ x y-2^w, \quad 2^w \le xy \le 2^{w1}-2 \end{cases} \end{align} xwu​y{xy,xy−2w,​0≤xy≤2w−12w≤xy≤2w1−2​​​ 说一个算术运算溢出是指完整的整数结果不能被有限的整型长度所表示产生了高有效位的丢失。 执行C程序时系统不会因运算发生溢出而自己报错因此程序员必须关注该情况。 原理检测无符号加法中的溢出。 对满足0≤x,y≤2w−10 \le x,y \le 2^w-10≤x,y≤2w−1的x和y存在s˙xwuys.x^u_wys˙xwu​y当且仅当sxs xsxsysysy时运算发生了溢出。 证明当sxs xsxsysysy时运算发生了溢出。 因为x≥0x\ge 0x≥0因此xy≥yxy \ge yxy≥y因此s≥ys \ge ys≥y所以当sysysy时发生运算错误即溢出。 因为y≥0y \ge0y≥0因此xy≥xxy \ge xxy≥x因此s≥xs \ge xs≥x所以当sxsxsx时发生运算错误即溢出。证明当运算发生溢出时sxs xsxsysysy。 运算发生溢出时sxy−2wsxy-2^wsxy−2w因为y2wy2^wy2w因此y−2w0y-2^w0y−2w0因此sxsxsx。 运算发生溢出时syx−2wsyx-2^wsyx−2w因为x2wx2^wx2w因此x−2w0x-2^w0x−2w0因此sysysy。 对任何一个数xxx而言存在−x-x−x使得−xx0-xx0−xx0则称−x-x−x是xxx的加法逆元xxx也是−x-x−x的加法逆元。加法逆元即取反。 原理无符号数取反。 对满足0≤x≤2w−10 \le x \le 2^w-10≤x≤2w−1的x其w位的无符号加法逆元−wu-^u_w−wu​可表示为 −wux{x,x02w−x,x0\begin{align} -^u_wx \begin{cases} x,\quad x0\ 2^w-x,\quad x0 \end{cases} \end{align} −wu​x{x,2w−x,​x0x0​​​ 练习1 实现一个函数如果参数x和y相加不会产生溢出这个函数就返回1。 int uadd_ok(unsigned x, unsigned y) {unsigned s x y;return s x; }练习2 给出下表中数的无符号加法逆元 −4u-^u_4−4u​ 的位表示。 x-x十六进制十进制十六进制十进制0x000x000x550xB110x880x880xD130x330xF150x11 补码加法 对满足−2w−1≤x,y≤2w−1−1-2^{w-1} \le x,y \le 2^{w-1}-1−2w−1≤x,y≤2w−1−1的x和yx y的取值范围是−2w≤xy≤2w−2-2^w \le xy \le 2^w-2−2w≤xy≤2w−2。跟无符号加法一样当运算结果不能用w位表示时会截断数据产生运算溢出。 我们使用操作wt^t_wwt​表示w位的补码加法。 原理补码加法。 对满足−2w−1≤x,y≤2w−1−1-2^{w-1} \le x,y \le 2^{w-1}-1−2w−1≤x,y≤2w−1−1的xxx和yyy有 xwty{xy2w,xy−2w−1负溢出xy,−2w−1≤xy≤2w−1−1正常xy−2w,xy≥2w−1正溢出\begin{align} x^t_wy \begin{cases} xy2^w, \quad xy -2^{w-1} \quad 负溢出\ xy, \quad -2^{w-1} \le xy \le 2^{w-1}-1 \quad 正常 \ xy-2^w,\quad xy \ge 2^{w-1} 正溢出 \end{cases} \end{align} xwt​y⎩⎨⎧​xy2w,xy,xy−2w,​xy−2w−1−2w−1≤xy≤2w−1−1xy≥2w−1​负溢出正常正溢出​​​ 在bit层面无符号加法和补码加法的运算规则是一样的都是逢二进一。 负溢出指运算结果太小了小于−2w−1-2^{w-1}−2w−1正溢出指运算结果太大了大于2w−1−12^{w-1}-12w−1−1。溢出产生了符号翻转。 原理检测补码加法中的溢出。 对满足−2w−1≤x,y≤2w−1−1-2^{w-1} \le x,y \le 2^{w-1}-1−2w−1≤x,y≤2w−1−1的x和y存在s˙xys.xys˙xy。当且仅当x0x0x0y0y0y0s≤0s\le0s≤0时算术运算正溢出当且仅当x0x0x0y0y0y0s≥0s\ge0s≥0时算术运算负溢出。 证明x0x0x0y0y0y0s≤0s\le0s≤0时算术运算正溢出。 预期sxy0sxy0sxy0而s≤0s\le0s≤0显然s过大而无法表示运算产生了错误正溢出。证明算术运算正溢出因此x0x0x0y0y0y0时s≤0s\le0s≤0。 运算正溢出那么sxy−2wsxy-2^wsxy−2w且2w−1≤xy≤2w−22^{w-1}\le xy \le 2^{w}-22w−1≤xy≤2w−2因此x0x0x0y0y0y0且2w−1−2w≤s≤2w−2−2w2^{w-1}-2^w \le s \le 2^{w}-2-2^w2w−1−2w≤s≤2w−2−2w即−2w−1≤s≤−2≤0-2^{w-1} \le s \le -2 \le 0−2w−1≤s≤−2≤0即s≤0s\le0s≤0。证明x0x0x0y0y0y0s≥0s\ge0s≥0时算术运算负溢出。 预期sxy0sxy0sxy0而s≥0s\ge0s≥0显然s过小而无法表示运算产生了错误负溢出。算术运算负溢出因此x0x0x0y0y0y0时s≥0s\ge0s≥0。 运算负溢出那么sxy2wsxy2^wsxy2w且−2w≤xy−2w−1-2^{w}\le xy -2^{w-1}−2w≤xy−2w−1因此x0x0x0y0y0y0且−2w2w≤s≤−2w−12w-2^{w}2^w \le s \le -2^{w-1}2^w−2w2w≤s≤−2w−12w即0≤s≤2w−10 \le s \le 2^{w-1}0≤s≤2w−1即s≥0s\ge0s≥0。 练习1 填写下表 xxxyyyxyxyxyx5tx^t_5x5t​情况[10100]-12[10001]-15[100101]-27[00101]5负溢出[11000]-8[11000]-8[110000]-16[10000]-16正常[10111]-9[01000]8[11111]-1[11111]-1正常[00010]2[00101]5[00111]7[00111]7正常[01100]12[00100]4[10000]16[10000]-16正溢出 练习2 实现一个函数tadd_ok参数x和y补码相加不产生溢出时返回1。 int tadd_ok(int x, int y) {int s x y;return !((x 0 y 0 s 0) || (x 0 y 0 s 0)); }练习3 如下实现存在什么问题 int tadd_ok(int x, int y) {int sum x y;return (sum - x y) (sum - y x); }函数会永远返回1。因为并没有检测到越界的进位。 练习4 下面的函数在计算x - y不溢出时返回1。 int tsub_ok(int x, int y) {return tadd_ok(x, -y); }x和y取什么值时该函数会产生错误的结果写一个该函数的正确版本。 当y的取值为INT_MIN时-y的取值也为INT_MIN。因此在计算机看来x-y就是xy。 此时按现实的整数运算来看如果x 0x-y预期运算溢出返回0如果如果x 0x-y预期运算不溢出返回1。 但在计算机看来如果x 0tadd_ok(x, -y)不溢出返回1如果x 0tadd_ok(x, -y)溢出返回0。 我们以为它做的是减法实际上它做的是加法。 在计算机运算中INT_MIN的位级表示是[1, 0, …, 0]-INT_MIN的位级表示也是[1, 0, …, 0]因为[1, 0, …, 0] [1, 0, …, 0] [0, 0, …, 0]。当然这不符合现实的整数运算规则。 正确的写法如下 int tsub_ok(int x, int y) {if (y INT_MIN) {return !tadd_ok(x, -y);}return tadd_ok(x, -y); }补码的非 取非就是求加法逆元。 对满足TMinw≤x≤TMaxwTMin_w \le x \le TMax_wTMinw​≤x≤TMaxw​的x其补码的非−wtx-^t_wx−wt​x表示为 −wtx{TMinw,xTMinw−x,TMinwx≤TMaxw\begin{align} -^t_wx \begin{cases} TMin_w, \quad xTMin_w \ -x, \quad TMin_w x \le TMax_w \end{cases} \end{align} −wt​x{TMinw​,−x,​xTMinw​TMinw​x≤TMaxw​​​​ 在C语言中可以说对于任意整数值x因为x ~x 1 0所以-x ~x 1。 练习 填写下表。 xxx−4tx-^t_4x−4t​x0x000x000x550xB-50x8-80x8-80xD-30x330xF-10x11 无符号乘法 两个w位的无符号数相乘其结果可能需要2w个位才能完整表示。但在C语言中会根据整数位宽做截断处理。 对满足0≤x,y≤2w−10 \le x,y \le 2^w-10≤x,y≤2w−1的x和y有 x∗wuy˙(x∗y)mod2w\begin{align} x *^u_w y.(x * y) mod 2^w \end{align} x∗wu​y˙(x∗y)mod2w​​ 补码乘法 对满足−2w−1≤x,y≤2w−1−1-2^{w-1} \le x,y \le 2^{w-1}-1−2w−1≤x,y≤2w−1−1的x和y有 x∗wty˙U2Tw((x∗y)mod2w)\begin{align} x *^t_w y.U2T_w((x * y) mod 2^w) \end{align} x∗wt​y˙U2Tw​((x∗y)mod2w)​​ w位无符号乘法和w位补码乘法的运算结果的低w位是一样的区别在于解释这些位的方式。 练习1 填写下表位宽w3。 模式xxxyyyx∗yx*yx∗y截断的x*y无符号[100]4[101]5[010100]20[100]4补码[100]-4[101]-3[001100]12[100]-4无符号[010]2[111]7[001110]14[110]6补码[010]2[111]-1[111110]-2[110]-2无符号[110]6[110]6[100100]36[100]4补码[110]-2[110]-2[000100]4[100]4计算二进制w位的无符号乘法时先做零扩展扩展到2w位再两数相乘取低2w位。 计算二进制w位的补码乘法时先做符号扩展扩展到2w位再两数相乘取低2w位。 练习2 考虑下面的函数它判断两个参数是否会产生溢出不溢出返回1。 int tmul_ok(int x, int y) {int p x * y;return !x || p/x y; }当x 0时乘法不溢出函数返回1。和预期相符。 当x不等于0时 x∗ypt2wx*ypt2^wx∗ypt2w其中t≠0t\ne 0t0当且仅当计算溢出。 当t≠0t\ne 0t0时x∗ypx*ypx∗yp或者x∗ypx*ypx∗yp计算溢出。 如果计算溢出px∗ypx*ypx∗y或者px∗ypx*ypx∗y所以t≠0t\ne 0t0。px∗qrpx*qrpx∗qr其中q是p/xp/xp/x的结果|r| |x|。 r是p除以x的余数因此一定存在|r| |x|。q y当且仅当r t 0。 q y时x∗qpt2wx*qpt2^wx∗qpt2w因此x∗qrpt2wrx*qrpt2^wrx∗qrpt2wr因此ppt2wrppt2^wrppt2wr因此00t2wr00t2^wr00t2wr所以r t 0。 r t 0时x∗yx∗qt2wx*yx*qt2^wx∗yx∗qt2w因此yqt2wxyq\frac {t2^w}{x}yqxt2w​因此q y。 计算溢出时r≠0r \ne 0r0t≠0t \ne 0t0因此q≠yq\ne yqyp/x≠yp/x \ne yp/xy函数返回0。反之不溢出函数返回1。 练习3 对于数据类型int为32位的情况设计一个tmul_ok函数使用64位精度的数据类型int64_t不使用除法。不溢出返回1。 int tmul_ok(int x, int y) {int64_t p (int64_t)x * y;return p (int)p; // 截断前后的值是不是一样 }乘以常数 在大多数机器上整数乘法指令相当慢。因此编译器使用了一项重要的优化就是用移位和加减法运算的组合来代替与常数因子的乘法。当然如果数个移位和加减法指令比一个乘法指令更耗时那就用乘法指令。 一个整数乘以2k2^k2k等价于左移k位k≥0k \ge 0k≥0。 练习1 LEA指令能够执行如(a k) b这样的运算。考虑b 0或者b a、k为任意可能的值一条LEA指令可以计算a的哪些倍数 当b 0时一条LEA指令可以计算a的20,21,22,23,…2^0,2^1,2^2,2^3,…20,21,22,23,…倍。 当b a时一条LEA指令可以计算a的201,211,221,231,…2^0 1,2^1 1,2^2 1,2^3 1,…201,211,221,231,…倍。 练习2 填写下表。 kkk移位加法/减法表达式621(x3)−(x1)(x3)-(x1)(x3)−(x1)3111(x5)−x(x5)-x(x5)−x-621(x1)−(x3)(x1)-(x3)(x1)−(x3)5522(x6)−x−(x3)(x 6) - x - (x 3)(x6)−x−(x3) 除以2的幂 在大多数机器上整数除法比整数乘法还慢。 除以2的幂可以用右移实现无符号数使用逻辑右移有符号数使用算术右移。 对于任何实数α\alphaα定义⌈α⌉\lceil \alpha \rceil⌈α⌉为唯一的整数α′\alphaα′使得α′−1α≤α′\alpha-1 \alpha \le \alphaα′−1α≤α′。 对于任何实数α\alphaα定义⌊α⌋\lfloor \alpha \rfloor⌊α⌋为唯一的整数α′\alphaα′使得α′≤αα′1\alpha \le \alpha \alpha1α′≤αα′1。 对于x≥0,y0x\ge0,y0x≥0,y0xxx除以yyy的结果是⌊x/y⌋\lfloor x/y \rfloor⌊x/y⌋对于x0,y0x0,y0x0,y0或x0,y0x0,y0x0,y0xxx除以yyy的结果是⌈x/y⌉\lceil x/y \rceil⌈x/y⌉。即向零取整。 计算机执行除法运算时不论结果正负都是向下取整。 如果要向上取整需要给被除数加上偏置量除数-1。 ⌈x/y⌉⌊(xy−1)/y⌋\begin{align} \lceil x/y \rceil\lfloor (xy-1)/y \rfloor \end{align} ⌈x/y⌉⌊(xy−1)/y⌋​​ C表达式(x 0 ? x (1 k) - 1 : x) k将会计算x/2kx/2^kx/2k。 同乘法不同我们不能用右移和加减运算的组合表示除以任意常数。乘法满足分配律但除法不。 练习1 写一个函数div16返回x/16的结果。 int div16(int x) {int sign x 31; // 符号位填满intint k 4;int bias (1 k) - 1;return (x sign bias) k; }练习2 下面的代码中省略了M和N的定义。 int arith(int x, int y) {return x * M y / N; }编译器优化后 int arith(int x, int y) {int t x;x 5;x - t;if (y 0) {y 7;}y 3;return x y; }M和N的值是多少 M 31, N 8。 关于整数运算的最后思考 计算机执行的“整数”运算实际上是一种模运算因为整型的有限字长限制了可能的取值范围运算结果可能溢出。 无符号数与补码数在运算时拥有相同的位级行为区别在于编译器解释位的方式。 练习 int x foo(); int y bar(); unsigned ux x; unsigned uy y;对于下面的C表达式 1证明对于所有的x和y结果都为1。 2给出使他们为0的x和y。 (x0)∣∣(x−10)(x 0) || (x - 1 0)(x0)∣∣(x−10) 当x TMin时结果为0。(x 7) ! 7 || (x 29 0) x的低3位不都是1时结果是1。 x的低3位都是1时结果是1。(x∗x)0(x * x) 0(x∗x)0 运算可能会溢出当x 123456时x * x的低32位是1000 1100 0111 0101 0001 0000 0000 0000符号位是1是负数。x0∣∣−x0x 0 || -x 0x0∣∣−x0 如果x是非负数-x一定是非正的。x0∣∣−x0x 0 || -x 0x0∣∣−x0 如果x TMin-x还是TMin都是负数。xyuyyxx y uy yxxyuyyx 结果是1。无符号数与补码数有相同的位级行为且可交换。x * ~y uy * ux -x 结果是1。 补码表示中-y ~ y 1因此~ y -y - 1。 x * ~y uy * ux x * (-y - 1) uy * ux -xy - x uy * ux -x。