54

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

测试在这里。我不得不做一些杂技来编写有意义的代码，这些代码不会一起省略操作。

结论（暂时）

所以最后取决于关卡优化和表现力：

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

7 回答 7

50

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

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

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

于 2015-03-17T22:23:49.057 回答
37

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

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

于 2015-03-17T22:17:18.667 回答
7

首先，我所知道的最快的 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;
}
于 2015-03-19T09:08:25.573 回答
3

许多算法需要计算 (-1)^n （均为整数），通常作为系列中的一个因素。也就是说，奇数 n 为 -1，偶数 n 为 1。

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

于 2015-03-18T20:22:18.210 回答
2

如果你需要的速度，这里是...

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

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

于 2018-01-04T08:37:17.627 回答
1

关于什么

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

n%2很可能只计算一次

更新

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

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

return res[n%2 + 1];
于 2015-03-18T01:32:44.980 回答
1

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

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

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

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

于 2015-03-24T22:42:07.637 回答