获得(-1)^n的正确方法是什么？

Question

许多算法需要计算 (-1)^n（均为整数），通常作为数列中的一个因子。即，奇数 n 为 -1 偶数 n 为 1 的因数。在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)

编辑：

此外，用户@SeverinPappadeux 提出了另一种基于（全局？）数组查找的替代方法。我的版本是：

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) << 1);

（7次操作，无内存访问）

  mov eax, DWORD PTR [rbp-20]
  add eax, eax
  and eax, 2
  mov edx, 1
  sub edx, eax
  mov eax, edx
  mov DWORD PTR [rbp-16], eax

和

   retvals[n&1];

（5次操作，内存--寄存器？--访问）

  mov eax, DWORD PTR [rbp-20]
  and eax, 1
  cdqe
  mov eax, DWORD PTR main::retvals[0+rax*4]
  mov DWORD PTR [rbp-8], eax

现在有优化 (-O3)

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

（4次操作，无内存访问）

  add edx, edx
  mov ebp, 1
  and edx, 2
  sub ebp, edx

.

  retvals[n&1];

（4个操作，内存--寄存器？--访问）

  mov eax, edx
  and eax, 1
  movsx rcx, eax
  mov r12d, DWORD PTR main::retvals[0+rcx*4]

.

   n%2?-1:1;

（4次操作，无内存访问）

  cmp eax, 1
  sbb ebx, ebx
  and ebx, 2
  sub ebx, 1

测试是here。我不得不做一些杂技来获得有意义的代码，这些代码不会一起省略操作。

结论（暂时）

所以最后还是要看关卡优化和表现力：

1 - ((n & 1) << 1); 总是不错，但表现力不强。
retvals[n&1]; 为内存访问付出代价。
n%2?-1:1; 表现力好，但只有优化。

Answer 1

通常你不会实际计算 (-1)^n，而是跟踪当前符号（作为数字 -1 或 1）并在每次操作时翻转它（sign = -sign)，在按顺序处理 n 时执行此操作，您将得到相同的结果。

编辑：请注意，我推荐这个的部分原因是因为很少有实际的语义价值是表示(-1)^n它只是一种在迭代之间翻转符号的方便方法。

Answer 2

你可以使用 (n & 1) 代替 n % 2 和 << 1 代替 * 2 如果你想超级迂腐，呃我的意思是优化。
所以在 8086 处理器中最快的计算方式是：

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

我只是想澄清一下这个答案的来源。原始发帖人 alfC 出色地发布了许多不同的计算 (-1)^n 方法，有些方法比其他方法更快。
如今，随着处理器的速度越来越快，编译器的优化也越来越好，我们通常重视可读性，而不是削减几个 CPU 周期带来的轻微（甚至可以忽略不计）改进来自操作。
曾经有一段时间，一次性编译器统治了地球，而 MUL 操作是新的和颓废的；在那些日子里，2 的幂运算是无偿优化的邀请。

Answer 3

那

呢

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

n%2 很可能只计算一次

更新

实际上，最简单和最正确的方法是使用 table

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

return res[n%2 + 1];

Answer 4

Many algorithms require to compute (-1)^n (both integer), usually as a factor in a series. That is, a factor that is -1 for odd n and 1 for even n.

考虑将系列评估为 -x 的函数。

Answer 5

首先，我所知道的最快的 isOdd 测试（使用内联方法）

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

然后利用这个测试 return -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;
}

Answer 6

好吧，如果我们按系列执行计算，为什么不在正循环和负循环中处理计算，完全跳过评估？

近似于 (1+x) 自然对数的泰勒级数展开是此类问题的完美示例。每一项都有 (-1)^(n+1)，或 (1)^(n-1)。无需计算该系数。您可以 "slice" 通过对每两项执行 1 个循环或两个循环（一个用于奇数项，一个用于偶数项）来解决问题。

当然，由于计算本质上是实数域上的计算，因此无论如何您都将使用浮点处理器来计算各个项。一旦你决定这样做，你应该只使用自然对数的库实现。但如果出于某种原因，你决定不这样做，它肯定会更快，但不会快很多，不要浪费周期计算 -1 的 n 次方的值。

也许每个甚至可以在单独的线程中完成。也许问题可以向量化，甚至。

Answer 7

如果您需要速度，这里是...

int inline minus_1_pow(int n) {
    static const int retvals[] {1, -1}; 
    return retvals[n&1];
}

优化为 11 的 Visual C++ 编译器将其编译为两条机器指令，这两条指令都不是分支。它还优化了 retvals 数组，因此没有缓存未命中。

获得(-1)^n的正确方法是什么？

What is the correct way to obtain (-1)^n?

c++

algorithm

x86

cmath

编辑：

首先没有优化，最后的竞争者是：

现在有优化 (-O3)

结论（暂时）