从编译器除以2的幂说起 执行除法，是一种比较耗费性能的操作。但有一种类型除外。那就是除以2的幂。编译器会将除以$$2^n$$使用移位进行优化。 我们在编码时可以善于利用 $$2^n$$，比如数组/队列的长度、取余、相除的除数等最好都使用 $$2^n$$。说不定有意外的惊喜。在各类语言的标准库中，广泛的使用了这一优化。 ## 原码除以 2^n 当一个整数以原码表示时，除以2的幂也可以用移位运算来实现。 执行逻辑右移（前位补0）移位总是**舍入到零**的结果。 公式为： $$x/2^k = x>>k$$ <img src="https://share.superpig.win/img_share/edit-55f902ead4294db5a9b857197b5748ff/image-20230117155131336.png" alt="image-20230117155131336" style="zoom:50%;" /> > 图源：《深入理解计算机系统-第二章：信息的表示和处理 也就是说计算 $$6170/2^3$$ 等同于6170的原码 `0001100000011010`，右移3位，得到`000 0001100000011`。 其结果等于 771，而实际结果是 `6170/8 = 771.25`。 结果向0进行了舍入。 ## 补码除以 2^n 同理，补码有类似的性质。但需要进行算术右移，也就是前位补1。 <img src="https://share.superpig.win/img_share/edit-55f902ead4294db5a9b857197b5748ff/image-20230117155401056.png" alt="image-20230117155401056" style="zoom:50%;" /> > 图源：《深入理解计算机系统-第二章：信息的表示和处理》 `-6170`使用补码表示是：`1110011111100110`。 对其除以 $$2^3$$。**等同右移3位**，得到结果为：`-772`。但结果变成了 **向下舍入**。 回到前面的原码场景，`6170`进行除以8的**结果是 771**。 为了运算一致，可以在移位前，增加一个`偏置(biasing)`，使其也**向0舍入**，这也是go的默认处理方式。 偏置为： $$(2^k-1)$$ 此时，运算公式变为： $$x/2^k = (x+(2^k-1))>>k$$ 重新计算 $$-6170/2^3$$ `-6170`使用补码表示是：`1110011111100110`。 偏置 $$2^3-1$$ 使用补码表示是 `111` 相加：`1110011111101101 ` 算术右移得：`1111110011111101=-771`，此时就是向0舍入的结果。 ## 为什么偏置是 2^n-1 $$ 2^n-1 $$ 用二进制表示是，n个1。 比如$$2^3-1=b111$$ 1、假设最右边的n位是000...000，则加上n个1，再进行右移n位，这n个1不会有任何影响。因为正好能除尽。 例如计算 $$-8/2^2=-2$$ 解： $$-8=b11000$$ $$2^2 - 1=b11$$ $$-8+2^2-1=b11011 $$ 算术右移2位: $$b11110 = -2$$ 这说明，正好能除尽，也就没有向0舍入的问题。 2、假设最右边的n位是 111...111，加上n个1，再进行右移n位。 例如计算： $$-25/2^3=-3.125$$ 解： $$-25 = b100111$$ $$-25+2^k-1=b100111+111=b101110$$ 算术移位得： $$b111101 = -3$$ 这说明，增加偏置后，进行了一次进位。这个进位即是多出来的小数部分。**如果不加偏置**，直接算术右移，则结果为： $$b111100 = -4$$ 这就是-3.125向下舍入的结果。 ## 最后，看看汇编代码会变成什么样 ```c long arith(long x){ return x/8 } ``` <img src="https://share.superpig.win/img_share/20230807/image-20230807212816533.png" alt="image-20230807212816533" style="zoom:50%;" /> 这段代码计算了两个结果， 当x<0的时候，第二行汇编就是对 x 增加偏置 7。 当x>=0的时候，直接将x放在 %rax，这使得之前的带偏置的计算结果被丢弃，然后sarq，对 x 进行移位。 来自 大脸猪 写于 2023-08-08 15:28 -- 更新于2023-08-08 15:47 -- 0 条评论