java - 2的幂时如何将除法转换为按位移位？

Question

我有以下需要经常做的部门：

int index = pos / 64;

在 cpu 级别上除法可能很昂贵。我希望有一种方法可以通过按位移位来做到这一点。我还想了解如何从除法转换到移位，换句话说，我不想只记住按位表达式。

score 7 · Accepted Answer

int index = pos >> 6会这样做，但这是不必要的。任何合理的编译器都会为你做这种事情。Sun/Oracle 编译器当然会。

一般规则是i/(2^n)可以用i >> n. 同样i*(2^n)是i << n。

i如果已签名，您需要关注负数表示。例如，二进制补码产生合理的结果（如果右移是算术 - 符号位复制）。有符号的幅度没有。

score 2 · Accepted Answer

编译器将以最有效的方式为您实现它，只要您了解您需要什么并要求编译器准确地做到这一点。如果在这种情况下 shift 是最有效的方式，编译器将使用 shift。

但请记住，如果您正在执行有符号除法（即pos有符号），那么仅靠班次就无法完全实现。Shift 本身会为的负值生成无效结果pos。如果编译器决定对该操作使用移位，它还必须对中间结果执行一些移位后更正，以使其符合语言规范的要求。

出于这个原因，如果您真的在寻找除法操作的最大可能效率，您必须记住不要轻率地使用有符号类型。尽可能使用无符号类型，仅在必要时使用有符号类型。

PS AFAIK，Java实现欧几里得除法，意思是上面的评论不适用于Java。欧几里得除法是通过在 2 的补码表示中对负除数进行移位来正确执行的。上述说明适用于 C/C++。

score 0 · Accepted Answer

对于要除以的每个 2 的幂，将其右移一次。所以除以 4 你会右移两次。除以 8 右移 3 次。除以 16 右移 4 次。32 -> 5 次。64 -> 6 次。所以除以 64 你可以右移 6 次。我的价值 = 我的价值 >> 6;

3 回答 3