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

What is the fastest way to find if a number is even or odd?

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

11 个解决方案

#1

It is pretty well known that

这是众所周知的

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

is more efficient than

是更有效的比

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

But with the optimizer on, will is_odd_B be no different from is_odd_A? No — with gcc-4.2 -O2, we get, (in ARM assembly):

但是有了优化器，is_odd_B和is_odd_A没有什么区别吗?No -有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

We see that is_odd_B takes 3 more instructions than is_odd_A, the main reason is because

我们看到is_odd_B比is_odd_A需要更多的指令，主要原因是。

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

However, all the following versions will generate the same code as is_odd_A:

但是，以下所有版本将生成与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 !=

What does this mean? The optimizer is usually sophisticated enough that, for these simple stuff, the clearest code is enough to guarantee best efficiency.

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

#2

Usual way to do it:

通常的做法是:

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

Alternative:

选择:

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

Tested on GCC 3.3.1 and 4.3.2, both have about the same speed (without compiler optimization) as both result in the and instruction (compiled on x86) - I know that using the div instruction for modulo would be much slower, thus I didn't test it at all.

在GCC 3.3.1和4.3.2上测试过，两者的速度都差不多(没有编译器优化)，结果都是and指令(在x86上编译)——我知道对modulo使用div指令会慢得多，因此我根本没有测试它。

#3

bool is_odd = number & 1;

#4

if (x & 1) is true then it's odd, otherwise it's even.

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

#5

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

#6

If it's an integer, probably by just checking the least significant bit. Zero would be counted as even though.

如果它是一个整数，可能只需检查最不重要的位。0可以被看成是偶数。

#7

The portable way is to use the modulus operator %:

移动方式是使用模量算符%:

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

If you know that you're only ever going to run on two's complement architectures, you can use a bitwise and:

如果你知道你只会运行两个补码架构，你可以使用一个位的和:

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

Using the modulus operator can result in slower code relative to the bitwise and; however, I'd stick with it unless all of the following are true:

使用模量运算符可以使代码相对于位元更慢;然而，除非以下所有的都是真的，否则我将坚持下去:

1. You are failing to meet a hard performance requirement;
2. 你没有达到严格的性能要求;
3. You are executing x % 2 a lot (say in a tight loop that's being executed thousands of times);
4. 您执行的是x % 2(在一个执行数千次的紧密循环中);
5. Profiling indicates that usage of the mod operator is the bottleneck;
6. 分析表明，使用mod操作符是瓶颈;
7. Profiling also indicates that using the bitwise-and relieves the bottleneck and allows you to meet the performance requirement.
8. 分析还表明，使用位元可以缓解瓶颈，并允许您满足性能需求。

#8

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

Oh wait, you said fastest way, not funniest. My bad ;)

哦，等等，你说的是最快的方式，不是最好笑的。我的坏。

Above function only works for positive numbers of course.

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

#9

Check to see if the last bit is 1.

检查最后一个位是否为1。

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

#10

Check the least significant bit:

检查最不重要的位:

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

#11

Your question is not completely specified. Regardless, the answer is dependent on your compiler and the architecture of your machine. For example, are you on a machine using one's complement or two's complement signed number representations?

你的问题没有完全说明。无论如何，答案取决于编译器和机器的体系结构。例如，您是使用one's的补码还是使用two的补码符号?

I write my code to be correct first, clear second, concise third and fast last. Therefore, I would code this routine as follows:

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

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

This method is correct, it more clearly expresses the intent than testing the LSB, it's concise and, believe it or not, it is blazing fast. If and only if profiling told me that this method were a bottleneck in my application would I consider deviating from it.

这种方法是正确的，它比测试LSB更清楚地表达了意图，它是简洁的，信不信由你，它非常迅速。如果并且只有当分析告诉我这个方法在我的应用程序中是一个瓶颈时，我才会考虑偏离它。