c++ - 计数倒置归并排序算法中的移位

Question

所以我找到了this implementation一种用于计算倒置的算法。一般来说我理解它，但我不确定为什么作者使用 shift 来寻找中点int mid=(low+((high-low)>>1)); 有人可以解释一下吗？提前致谢。

Answer 1

编写 int mid=(low+((high-low)>>1)); 的“明显”方式是 int mid=(low+high)/2;。后者有两个不足。

1. 整数溢出。如果数组很长，low+high 会溢出 int 的边界，这在 C++ 中是未定义的行为。在 Java 中，这是 infamous bug 的根本原因。 .

2. 效率。好的编译器不会发出(昂贵的)除以二的除法指令。然而，除非编译器能够以某种方式推断出 low+high 不是负数，否则它不能只是将除法(即，根据 C++ 标准截断除法)重写为移位(相当于底除法) ，因为负股息的结果不同。通常它会发出指令来计算符号位并将其添加进去，这需要一些额外的指令(尽管是便宜的指令)。