55

找出一个数字是偶数还是奇数的最快方法是什么？

4

11 回答 11

71

众所周知，

static inline int is_odd_A(int x) { return x & 1; }

比

static inline int is_odd_B(int x) { return x % 2; }

但是随着优化器的开启，会不会is_odd_B有什么不同is_odd_A？不——用gcc-4.2 -O2，我们得到，（在 ARM 汇编中）：

_is_odd_A:
    and r0, r0, #1
    bx  lr

_is_odd_B:
    mov r3, r0, lsr #31
    add r0, r0, r3
    and r0, r0, #1
    rsb r0, r3, r0
    bx  lr

我们看到它is_odd_B需要多 3 条指令is_odd_A，主要原因是因为

((-1) % 2) == -1
((-1) & 1) ==  1

但是，以下所有版本都将生成与以下相同的代码is_odd_A：

#include <stdbool.h>
static inline bool is_odd_D(int x) { return x % 2; }      // note the bool
static inline int  is_odd_E(int x) { return x % 2 != 0; } // note the !=

这是什么意思？优化器通常足够复杂，对于这些简单的东西，最清晰的代码就足以保证最佳效率。

于 2010-02-09T15:00:19.313 回答
7

通常的做法：

int number = ...;
if(number % 2) { odd }
else { even }

选择：

int number = ...;
if(number & 1) { odd }
else { even }

在 GCC 3.3.1 和 4.3.2 上测试，两者的速度都差不多（没有编译器优化），因为两者都导致and指令（在 x86 上编译） - 我知道使用div模数指令会慢得多，因此我没有根本不测试它。

于 2010-02-09T13:00:16.987 回答
6 
bool is_odd = number & 1;
于 2010-02-09T12:58:25.740 回答
5

如果 (x & 1) 为真，则为奇数，否则为偶数。

于 2010-02-09T12:57:43.417 回答
2 
int i=5;
if ( i%2 == 0 )
{
   // Even
} else {
   // Odd
}
于 2010-02-09T12:57:18.897 回答
2

如果它是一个整数，可能只检查最低有效位。即便如此，也将被视为零。

于 2010-02-09T12:57:58.530 回答
2

检查最后一位是否为 1。

int is_odd(int num) {
  return num & 1;
}
于 2010-02-09T12:59:17.783 回答
2 
int is_odd(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return !is_odd(n - 1);
}

哦等等，你说的是最快的方式，不是最有趣的。我的错 ;）

当然，上述功能仅适用于正数。

于 2010-02-09T14:30:08.877 回答
2

可移植的方法是使用模运算符%：

if (x % 2 == 0) // number is even

如果您知道您只会在二进制补码架构上运行，您可以使用按位和：

if (x & 0x01 == 0) // number is even

使用模运算符可能会导致相对于按位和的代码变慢；但是，除非满足以下所有条件，否则我会坚持下去：

  1. 您未能满足硬性能要求；
  2. 你执行x % 2了很多（比如说在一个被执行数千次的紧密循环中）；
  3. Profiling 表明 mod 运算符的使用是瓶颈；
  4. 分析还表明，使用按位和缓解瓶颈并允许您满足性能要求。
于 2010-02-09T14:49:25.693 回答
1

您的问题没有完全指定。无论如何，答案取决于您的编译器和您机器的架构。例如，您是在使用一个补码还是二进制补码有符号数表示的机器上？

我写我的代码首先是正确的，其次是清晰的，第三是简洁的，最后是快速的。因此，我将对该例程进行如下编码：

/* returns 0 if odd, 1 if even */
/* can use bool in C99 */
int IsEven(int n) {
    return n % 2 == 0;
}

这种方法是正确的，它比测试 LSB 更清楚地表达了意图，它很简洁，信不信由你，它的速度非常快。当且仅当分析告诉我这种方法是我的应用程序的瓶颈时，我才会考虑偏离它。

于 2010-02-09T14:30:09.107 回答
0

检查最低有效位：

if (number & 0x01) {
  // It's odd
} else {
  // It's even
}
于 2010-02-09T12:59:43.897 回答