Каков правильный способ получить (-1) ^ n?

Многим алгоритмам требуется вычислить (-1)^n (оба целых), как правило, в виде ряда. То есть коэффициент -1 для нечетных n и 1 для четного n. В среде C или С++ часто видят:

#include<iostream>
#include<cmath>
int main(){
   int n = 13;
   std::cout << std::pow(-1, n) << std::endl;
}

Что лучше или обычное соглашение? (или что-то еще),

std::pow(-1, n)
std::pow(-1, n%2)
(n%2?-1:1)
(1-2*(n%2))  // (gives incorrect value for negative n)

EDIT: Кроме того, пользователь @SeverinPappadeux предложил другую альтернативу, основанную на поиске массива (global?). Моя версия:

const int res[] {-1, 1, -1}; // three elements are needed for negative modulo results
const int* const m1pow = res + 1; 
...
m1pow[n%2]

Ответы

Ответ 1

Вы можете использовать (n & 1) вместо n % 2 и << 1 вместо * 2, если вы хотите быть супер-педантичным, я имею в виду оптимизированный.
Таким образом, самый быстрый способ вычислить в процессоре 8086:

1 - ((n & 1) << 1)

Я просто хочу уточнить, откуда этот ответ. Оригинальный плакат alfC сделал отличную работу по размещению множества различных способов вычисления (-1) ^ n, которые были быстрее других.
В настоящее время процессоры так же быстры, как и они, и оптимизация компиляторов настолько же хороша, как и они, мы обычно ценим читаемость над небольшими (даже незначительными) улучшениями от бритья нескольких циклов процессора от операции.
Было время, когда один прогон компиляторов правил землей, и операции MUL были новыми и декадентскими; в те дни сила 2 операции была приглашением на безвозмездную оптимизацию.

Ответ 2

Обычно вы на самом деле не вычисляете (-1)^n, вместо этого вы отслеживаете текущий знак (как номер, являющийся либо -1, либо 1), и переверните его каждую операцию (sign = -sign), сделайте это при обработке ваш n по порядку, и вы получите тот же результат.

EDIT: обратите внимание, что часть причины, которую я рекомендую, это потому, что редко существует семантическое значение, это представление (-1)^n, это просто удобный способ переворота знака между итерациями.

Ответ 3

Прежде всего, самый быстрый тест isOdd, который я знаю (в встроенном методе)

/**
* Return true if the value is odd
* @value the value to check
*/
inline bool isOdd(int value)
{
return (value & 1);
}

Затем используйте этот тест для возврата -1, если нечетный, 1 в противном случае (который является фактическим выходом (-1) ^ N)

/**
* Return the computation of (-1)^N
* @n the N factor
*/
inline int minusOneToN(int n)
{
return isOdd(n)?-1:1;
}

Последний, как было предложено @Guvante, вы можете сэкономить умножение, просто перевернув знак значения (избегая использования функции minusOneToN)

/**
* Example of the general usage. Avoids a useless multiplication
* @value The value to flip if it is odd
*/
inline int flipSignIfOdd(int value)
{
return isOdd(value)?-value:value;
}

Ответ 4

Многим алгоритмам требуется вычислить (-1) ^ n (оба целых), как правило, как фактор в ряду. То есть коэффициент, равный -1 для нечетных n и 1 для даже n.

Рассмотрим оценку ряда как функцию -x вместо.

Ответ 5

Что насчет

(1 - (n%2)) - (n%2)

n%2 скорее всего будет вычислен только один раз

ОБНОВЛЕНИЕ

Собственно, самым простым и правильным способом было бы использовать таблицу

const int res[] {-1, 1, -1};

return res[n%2 + 1];

Ответ 6

Хорошо, если мы выполняем вычисление в серии, почему бы не обрабатывать вычисления в положительном цикле и отрицательном цикле, полностью пропустив оценку?

Разложение в ряд Тейлора для аппроксимации натурального логана (1 + x) является прекрасным примером такого типа проблемы. Каждый член имеет (-1) ^ (n + 1) или (1) ^ (n-1). Нет необходимости вычислять этот коэффициент. Вы можете "разрезать" проблему, выполнив 1 цикл для каждых двух терминов или двух циклов, один для нечетных терминов и один для четных.

Конечно, поскольку вычисление, по своей природе, одно над областью действительных чисел, вы будете использовать процессор с плавающей запятой для оценки отдельных терминов в любом случае. После того, как вы решили это сделать, вы должны просто использовать реализацию библиотеки для естественного логарифма. Но если по какой-то причине вы решите не делать этого, это, конечно, будет быстрее, но не намного, а не тратить циклы, вычисляя значение -1 до n-й мощности.

Возможно, каждый может быть выполнен в отдельных потоках. Возможно, проблема может быть даже векторизована.