Что состоит в том, чтобы найти самый быстрый путь, даже ли число или нечетно?
Что состоит в том, чтобы найти самый быстрый путь, даже ли число или нечетно?
11 ответов
Хорошо известно, что
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 !=
Что это означает? Оптимизатор обычно достаточно сложен, чтобы для этих простых вещей самого чистого кода было достаточно, чтобы гарантировать максимальную эффективность .
Обычный способ:
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 для модуля было бы значительно медленнее, поэтому я не тестировал его вообще.
int i=5;
if ( i%2 == 0 )
{
// Even
} else {
// Odd
}
Если это целое число, возможно, просто проверяя младший значащий бит. Ноль будет считаться даже если.
Проверьте, равен ли последний бит 1.
int is_odd(int num) {
return num & 1;
}
переносимый способ - использовать оператор модуля % :
if (x % 2 == 0) // number is even
Если вы знаете , что вы собираетесь работать только на двух дополнительных архитектурах, вы можете использовать побитовое и:
if (x & 0x01 == 0) // number is even
Использование оператора модуля может привести к более медленный код относительно побитового и; однако я бы придерживался его, если не выполняются все следующие условия:
- Вы не выполняете жесткие требования к производительности;
- Вы выполняете
x% 2лот (скажем, в замкнутом цикле, который выполняется тысячи раз); - Профилирование указывает на то, что использование оператора mod является узким местом;
- Профилирование также указывает, что использование побитового - и устраняет узкое место и позволяет удовлетворить требования к производительности.
int is_odd(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return !is_odd(n - 1);
}
Ой, подождите, вы сказали самый быстрый способ, а не самый смешной . Моя проблема;)
Вышеупомянутая функция, конечно, работает только для положительных чисел.
Ваш вопрос не уточняется полностью. В любом случае ответ зависит от вашего компилятора и архитектуры вашей машины. Например, используете ли вы на компьютере представление числа со знаком дополнения или дополнения до двух?
Я пишу свой код так, чтобы сначала был правильный, затем четкий, затем - краткий, а затем - быстрый. Поэтому я бы закодировал эту подпрограмму следующим образом:
/* returns 0 if odd, 1 if even */
/* can use bool in C99 */
int IsEven(int n) {
return n % 2 == 0;
}
Этот метод правильный, он более четко выражает намерение, чем тестирование LSB, он краток и, хотите верьте, хотите нет, он очень быстр. Если бы и только если бы профилирование сказало мне, что этот метод является узким местом в моем приложении, я бы подумал об отклонении от него.
Проверка наименее значимого бита:
if (number & 0x01) {
// It's odd
} else {
// It's even
}