检查奇数和按 2 的幂执行除法的最快方法是什么

Question

出于各种原因，通常需要检查一个完整数字的奇数，一个这样的例子是数据网格，其中每条奇数行都是不同的颜色以提高可读性。程序员经常使用公式

来实现这样的功能

odd = n mod 2 != 0

或反过来：

even = n mod 2 == 0

但是这种方法很慢，因为它需要 FPU 计算除法的余数。

我还看到开发人员编写了以下代码：

x = n / 2
odd = x mod 2

有更好的方法吗？

Answer 1

这个问题的答案很简单但经常被忽视，请注意这只适用于整数，而不适用于浮点数。

要让 x86 上的 FPU CPU 执行 division/modulus 计算，单精度至少需要 17 个时钟周期，双精度至少需要 34 个时钟周期。

所以我们可以很好地了解上面代码中更复杂的示例需要多少个周期（最好的情况不计算 CPU load/store 操作）。

x = n / 2      17 cycles
odd = x mod 2  17 cycles
               ---------
               34 cycles

因为计算机用二进制表示整数，我们可以通过检查第一位是否设置来简单地检查数字是否为奇数，这适用于任何支持位运算的语言。

例如：

Psuedo Code: odd = n and 1
C/C++/Java : odd = n & 1;

掩码操作只需要 1 个周期，根据 FPU 模式，每个 division/modulus 操作 的性能提高 17 到 34 倍。

对于第二个例子中的除以2，可以使用位操作来执行，实际上，任何除以2的幂都可以使用位右移操作来执行。例如：

Psuedo Code: x = n shr 1
C/C++/Java : x = n >> 1;

这会将 n 中的所有位向右移动一位，从而执行除以 2，如果向右移动两位，则将除以 4。这可以反向以二的幂相乘，但通常不以这种方式使用，因为乘法运算同样快。

如果我们结合这两种技术，我们可以将第二个示例更改为：

Psuedo Code:
  x = n shr 1
  odd = x and 1

C/C++/Java:
  x = n >> 1;
  odd = x & 1;

这可以进一步简化为

Psuedo Code: odd = (n shr 1) and 1
C/C++/Java : odd = (n >> 1) & 1;

与使用 FPU 的版本相比，此版本总共仅使用两个时钟周期来执行数学运算，性能提高了 1700%。

许多编译器都知道这些技巧，并且会在适合您的情况下以这种方式编译代码，但是许多脚本语言并不那么聪明，而且并非所有编译器都是平等的。

例如，编译器可能无法接受以下示例用法：

int doMath(int x, int y) {
  return x / y;
}

doMath(10, 2);
doMath(20, 4);  
doMath(30, 8);

但是如果它是用幂来写的，它总是会更快，即：

int doMath(int x, int y) {
  return x >> y;
}

doMath(10, 1);
doMath(20, 2);
doMath(30, 3);

如果你学习并利用这些技巧，你将编写出非常高效的代码，在任何地方都运行良好，而不必猜测编译器是否会为你创建良好的输出，尤其是当你在 Microsoft/Intel 和 Microsoft/Intel 之间交叉编译代码时在与平台无关的项目中经常使用 GCC。

What is the fastest way to check for oddness & perform divisions by powers of 2