判断一个数是偶数还是奇数的最快方法是什么？

Question

判断一个数是偶数还是奇数的最快方法是什么？

Answer 1

众所周知，它

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

比 is_odd_A 更高效，

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 比 is_odd_A 多需要 3 条指令，主要原因是因为

((-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 !=

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

Answer 2

通常的方法：

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

替代方案：

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

在 GCC 3.3.1 和 4.3.2 上进行测试，两者的速度大致相同（没有编译器优化），因为两者都会产生 和 指令（在 x86 上编译） -我知道使用 div 指令进行取模会慢很多，因此我根本没有测试它。

Answer 3

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

Answer 4

bool is_odd = number & 1;

Answer 5

int i=5;
if ( i%2 == 0 )
{
   // Even
} else {
   // Odd
}

Answer 6

int is_odd(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return !is_odd(n - 1);
}

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

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

Answer 7

检查最后一位是否为 1。

int is_odd(int num) {
  return num & 1;
}

Answer 8

你的问题没有完全具体化。无论如何，答案取决于您的编译器和机器的体系结构。例如，您使用的计算机是否使用补码或二进制补码有符号数字表示形式？

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

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

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

Answer 9

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

Answer 10

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

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

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

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

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

1. 您无法满足严格的性能要求；
2. 您正在执行x % 2很多（比如在一个被执行数千次的紧密循环中）；
3. 分析表明 mod 运算符的使用是瓶颈；
4. 分析还表明使用按位和可以缓解瓶颈并且使您能够满足性能要求。

Answer 11

检查最低有效位：

if (number & 0x01) {
  // It's odd
} else {
  // It's even
}

Answer 12

如果输入以 10 为基数，您不能只查看最后一位数字并检查它是偶数还是奇数吗？

{1, 3, 5, 7, 9} 为奇数

{0, 2, 4, 6, 8} 为偶数

其他信息： OP 指出一个数字是给定的，所以我在构建这个答案时遵循了这一点。这还要求数字以 10 为基数。根据以 10 为基数的偶数/奇数定义，该答案在数学上是正确的。根据用例，只需检查最后一位数字即可获得数学上一致的结果。

注意：如果您的输入已经是int，则只需检查其低位即可。这个答案仅对表示为数字序列的数字有用。您可以转换int->string来执行此操作，但这会比n % 2 == 0慢得多。

检查最后一位数字确实适用于任何偶数基数的数字字符串，而不仅仅是 10。对于低于 10 的基数，例如基数 8（八进制），9 和 8 不是可能的数字，但低位数字是奇数或偶数仍然判断是否是整数。

对于高于 10 的基数，会有额外的可能性，但无论如何您都不想搜索列表，只需使用正常的 i % 2 == 0i % 2 == 0检查作为整数的数字是奇数还是偶数code> 或 !=0 检查。

对于使用 'a' .. 'f' 表示数字值 10 到 15 的 ASCII 十六进制，ASCII 代码的低位不表示奇数或偶数，因为 'a' == 0x61 （奇数）但代表 10 又名 0xa （偶数）。因此，您必须将十六进制数字转换为整数，或者对 ASCII 代码进行一些位修改，以根据其他位或条件翻转低位。