Какой самый быстрый способ узнать, является ли число четным или нечетным?

Question

Какой самый быстрый способ узнать, является ли число четным или нечетным?

Answer 1

Хорошо известно, что

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

Что это значит? Оптимизатор, как правило, достаточно сложен, чтобы для этих простых вещей самого ясного кода было достаточно, чтобы гарантировать лучшую эффективность .

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, оба имеют примерно одинаковую скорость (без оптимизации компилятора), так как оба результата приводят к инструкции and (скомпилированной на x86) - я знаю, что использование инструкции div по модулю было бы намного медленнее, поэтому я вообще не проверял.

Answer 3

bool is_odd = number & 1;

Answer 4

если (x & 1) верно, то это нечетно, в противном случае - четно.

Answer 5

Способ portable заключается в использовании оператора модуля %:

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

Если вы знаете , что вы когда-либо собираетесь работать только на двух дополнительных архитектурах, вы можете использовать побитовое и:

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

Использование оператора модуля может привести к более медленному коду относительно побитового и; тем не менее, я бы придерживался этого, если все следующее не верно:

1. Вы не соответствуете жестким требованиям к производительности;
2. Вы выполняете x % 2 a лот (скажем, в тесном цикле, который выполняется тысячи раз);
3. Профилирование означает, что использование оператора мода является узким местом;
4. Профилирование также указывает, что использование побитового и освобождает узкое место и позволяет удовлетворить требования к производительности.

Answer 6

Проверьте, равен ли последний бит 1.

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

Answer 7

Если это целое число, возможно, просто проверяя младший значащий бит. Ноль будет считаться, хотя бы.

Answer 8

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

Answer 9

Ваш вопрос не полностью указан. Независимо от того, ответ зависит от вашего компилятора и архитектуры вашей машины. Например, находитесь ли вы на компьютере, использующем одно или два подписанных представления числа с дополнением?

Я пишу свой код, чтобы он был правильным первым, ясным вторым, кратким третьим и быстрым последним. Поэтому я бы закодировал эту процедуру следующим образом:

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

Этот метод верен, он более четко выражает намерение, чем тестирование LSB, он лаконичен и, верите или нет, он горит быстро. Если и только если профилирование скажет мне, что этот метод является узким местом в моем приложении, я бы подумал об отклонении от него.

Answer 10

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

Ой, подождите, вы сказали самый быстрый способ, а не самый смешной . Мой плохой;)

Вышеуказанная функция работает, конечно, только для положительных чисел.