从编译器除以2的幂说起

执行除法，是一种比较耗费性能的操作。但有一种类型除外。那就是除以2的幂。编译器会将除以

使用移位进行优化。

我们在编码时可以善于利用

，比如数组/队列的长度、取余、相除的除数等最好都使用

。说不定有意外的惊喜。在各类语言的标准库中，广泛的使用了这一优化。

原码除以 2^n

当一个整数以原码表示时，除以2的幂也可以用移位运算来实现。

执行逻辑右移（前位补0）移位总是舍入到零的结果。

公式为：

<img src="https://share.superpig.win/img_share/edit-55f902ead4294db5a9b857197b5748ff/image-20230117155131336.png" alt="image-20230117155131336" style="zoom:50%;" />

> 图源：《深入理解计算机系统-第二章：信息的表示和处理

也就是说计算

等同于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。

对其除以

。等同右移3位，得到结果为：-772。但结果变成了 向下舍入。

回到前面的原码场景，6170进行除以8的结果是 771。

为了运算一致，可以在移位前，增加一个偏置(biasing)，使其也向0舍入，这也是go的默认处理方式。

偏置为：

此时，运算公式变为：

重新计算

-6170使用补码表示是：1110011111100110。

偏置

使用补码表示是 111

相加：1110011111101101

算术右移得：1111110011111101=-771，此时就是向0舍入的结果。

为什么偏置是 2^n-1

用二进制表示是，n个1。

比如

1、假设最右边的n位是000...000，则加上n个1，再进行右移n位，这n个1不会有任何影响。因为正好能除尽。

例如计算

解：

算术右移2位:

这说明，正好能除尽，也就没有向0舍入的问题。

2、假设最右边的n位是 111...111，加上n个1，再进行右移n位。

例如计算：

解：

算术移位得：

这说明，增加偏置后，进行了一次进位。这个进位即是多出来的小数部分。如果不加偏置，直接算术右移，则结果为：

这就是-3.125向下舍入的结果。

最后，看看汇编代码会变成什么样

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 进行移位。