北邮CSAPP第二章之整数运算

2024-01-24 10:21:08

整数运算

两个非负整数的加法很有可能会导致溢出
两数相加后，丢弃超越范围的数字，得到的结果类似于模运算
例如9 + 12 = .21 = [10101] => [0101] = 5 = 21 % 16
丢弃最高位相当于从和中减去2^w(无符号)
C语言不会因为溢出而发出信号
检测溢出的方法：s = x + y(截取后), 若s < x或s < y，则发生了溢出
(不是很理解)阿贝尔群：对于无符号数，必有y使得x + y = 0(均限定在一定字节内)，则y = (x = 0) => x; (x > 0) => 2^w - x
(x + y) - x总能求到y，与是否溢出无关

使用截断的方法避免数据大小的不断扩张
正溢出，则结果为负数
负溢出，则结果为正数
x + y = {
x + y − 2 w 正溢出 x + y - 2^w 正溢出 x+y−2w正溢出
x + y 正常 x + y 正常 x+y正常
x + y + 2 w 负溢出 x + y + 2^w 负溢出 x+y+2w负溢出
}
大部分机器使用一模一样的指令执行无符号或者有符号的加法
将参数转换为无符号数，执行无符号数加法，再转化为补码
x + y = U2Tw[(x + y) mod 2^w]
检测补码加法溢出方法
s = x + y s = x + y s=x+y
x > 0 && y > 0 && s <= 0 => 正溢出
x < 0 && y < 0 && s >= 0 => 负溢出
总结：x、y同号且不等于0时，s == 0，或s与x、y任意异号，则溢出

TMin <= x <= TMax中，x的非：
{
x = T M i n = > T M i n x = TMin => TMin x=TMin=>TMin
x > T M i n = > − x x > TMin => -x x>TMin=>−x
}
对w位的补码加法，TMin是加法的逆
其它任意数值的x，都有-x作为加法的逆(整数非)
补码非的位级表示

将一个无符号数截断为w位等价于计算该值模2^w
无符号乘法：
x ⋅ y （无符号乘法） = ( x ⋅ y ) m o d 2 w x · y（无符号乘法） = (x · y)mod 2^w x⋅y（无符号乘法）=(x⋅y)mod2w

x ⋅ y = U 2 T w ( ( x ⋅ y ) m o d 2 w ) x · y = U2Tw((x · y)mod 2^w) x⋅y=U2Tw((x⋅y)mod2w)
对于无符号与补码乘法来说，乘法运算的位级表示都是一样的
对malloc进行乘法溢出验证：
malloc(ele_cnt * ele_size)
当ele_cnt * ele_size过大时，将溢出，例如
( 2 20 + 1 ) × 2 12 = 4096 （ 32 位机器） (2^{20} + 1) × 2^{12} = 4096（32位机器） (220+1)×212=4096（32位机器）

整数乘法相当慢（比起其它指令）（包括移位）
优化：使用移位和加法运算的组合来代替乘以常数因子的乘法
也就是说，先考虑乘以2的情况，再概括成乘以任意常数
x < < k < = > x ⋅ 2 k x << k <=> x · 2^k x<<k<=>x⋅2k
无论是通过无符号运算还是补码运算，乘以2的幂都可能导致溢出
因为乘法的代价太大，因此编译器会将乘法指令重写为加法与移位混合的运算
形式A： ( x < < n ) + ( x < < ( n − 1 ) ) + . . . + ( x < < m ) (x << n) + (x << (n - 1)) + ... + (x << m) (x<<n)+(x<<(n−1))+...+(x<<m)
形式B： ( x < < ( n + 1 ) ) − ( x < < m ) (x << (n + 1)) - (x << m) (x<<(n+1))−(x<<m)(连续的1)
y = 2 n + 2 ( n − 1 ) + . . . + 2 m = 2 ( n + 1 ) − 2 m y = 2^n + 2 ^ {(n - 1)} + ... + 2^m = 2^{(n + 1)} - 2^m y=2n+2(n−1)+...+2m=2(n+1)−2m

在大多数机器上，整数除法比整数乘法更慢：需要大概30个时钟周期
初以2的幂也可以使用移位运算实现（右移）：x >> k => x / 2^k
整数除法总是舍入到0：向下舍入一个正值，向上舍入一个负值
对无符号整数使用移位：一定是逻辑移位
移位总是舍入到0的结果
无符号整数除法： x = 2 k x ′ + x ′ ′ x = 2^kx' + x'' x=2kx′+x′′， x ′ ′ x'' x′′为低k位的无符号数， x ′ x' x′为高w-k位的无符号数
即 x’ = x >> k
补码运算的除法

执行算术右移
x > = 0 x >= 0 x>=0时，效果与逻辑右移一致
x < 0 x < 0 x<0时，再舍入时将导致向下舍入，因此需要修改策略
x’：高w-k位的补码数，x’’：低k位的无符号数， x = 2 k x ′ + x ′ ′ x = 2^kx' + x'' x=2kx′+x′′
由4，x’ = x / 2^k向下取整，当为负数时不符合
通过增加偏置量来使其输出正确结果
结果： x / 2 k = ( x + ( 1 < < k ) − 1 ) > > k x / 2^k = (x + (1 << k) - 1) >> k x/2k=(x+(1<<k)−1)>>k（结果向上取整）
对于不需要舍入的情况，偏置量只影响将被舍入的低位；对于需要舍入的情况，将给高位加1，结果将向0舍入
补码运算的除法： ( x < 0 ? x + ( 1 < < k ) − 1 : x ) > > k (x < 0 ? x + (1 << k) - 1 : x) >> k (x<0?x+(1<<k)−1:x)>>k
利用的数学性质： x / y ( 向下取整 ) = ( x + y − 1 ) / y ( 向上取整 ) x / y(向下取整) = (x + y - 1) / y(向上取整) x/y(向下取整)=(x+y−1)/y(向上取整)