如何正确地获得(-1)^n？

Question

许多算法需要计算(-1)^n（其中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

and

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

(四则运算，无内存访问)

  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; 具有表达力且效果良好，但仅在优化时才如此。

- alfC

---

pow是一个浮点数函数，所以我会避免使用它。n%2 ? -1 : 1似乎是最简单明了的选择。 - M.M

另一种变体是(n&1) ? -1 : 1。一些人觉得这种写法不太容易理解，但是在它旁边加上注释可以澄清其含义，并且位掩码运算速度较快。 - pjs

在这种情况下，(n&1)? -1: 1 应该更快--虽然在一般情况下它不等价，因此可能不会自动优化。 - Ben Voigt

自 n%2 在此处立即转换为 bool，我预期代码生成是相同的。 - T.C.

@T.C.：可能是这样。但需要注意的是，式子 1 - 2*(n&1) 是正确的，而问题中的 (1 - 2*(n%2)) 可能会得出 -1、1 或者 3。 - Ben Voigt

Answer 1

您可以使用(n & 1)代替n % 2，使用<< 1代替* 2，如果您想要非常严谨，嗯，我是指优化。
因此，在8086处理器中最快的计算方式是：1 - ((n & 1) << 1)。

我只是想澄清一下这个答案的来源。原帖作者alfC做得非常好，他贴出了很多不同的计算(-1)^n的方法，其中一些比其他方法更快。
现在，由于处理器的速度和优化编译器越来越好，我们通常会更看重代码的可读性，而不是微小（甚至可以忽略不计）的操作优化所带来的改进。
曾经有一个时期，单遍编译器统治着世界，MUL操作还是新生事物；在那个时代，2的幂运算是优化的机会。

- Eli Algranti

---

根据C标准（对于非负的n），n<<1被定义为n*2，因此这与优化无关，而是与可读性有关。 - M.M

你会展示表明这是最快的方式的基准测试结果吗？ - juanchopanza

一款优秀的优化编译器可能不会编译((n&1)?-1:1)中的分支，但如果您自己能做到，为什么不呢？ - Lee Daniel Crocker

@juanchopanza 如果我有一个8086处理器和一个8086时代的C编译器，我会这样做，但现在没有必要，只需要看一下执行乘法与移位、整数余数与逻辑与所需的周期数即可。对于当前的编译器和现代1周期乘法处理器来说，这是更加棘手的。 - Eli Algranti

我想知道有多少人拥有8086处理器和8086年代的C编译器。建议使用位移代替整数乘以2似乎很奇怪，需要强烈警告。 - juanchopanza

Answer 2

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

编辑：需要注意的是，我建议采用这种方法的部分原因是因为在表示(-1)^n时很少有语义价值，它只是在迭代之间翻转符号的一种便捷方法。

- Guvante

---

不需要跟踪任何东西，结果是n的一个非常简单的函数。 - juanchopanza

是的，你会看到各种各样的东西，包括这个。这就是问题来源的一部分。 - alfC

@alfC：我会尝试修改，我的观点的一部分是实际定义更类似于“每隔一个成员翻转符号”，但将其表示为(-1)^n是方便的，因为这是数学符号且正确的。因此，这种方法与原始意图相匹配，而不像通常的技巧那样是一种变通方法。 - Guvante

如果你可以翻转符号：sign = -sign;，为什么要乘以 -1？ - Ruslan

这个回答提出了一个很好的观点！(-1)^n 很少有语义价值，这是完全正确的，也是最重要的观察点 :) - Ant

Answer 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;
}

- Flavien Volken

---

请注意，value&1 在负有符号整数的一补码上会出现问题。此外，任何好的编译器都可以有效地评估(bool)(value % 2)。(不过是作为整数的value % 2，因为它可能是-1、0或+1，所以需要检查符号位。) - Peter Cordes

Answer 4

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

考虑将该系列作为关于 -x 的函数进行评估。

- Ian Ollmann

Answer 5

如果你需要速度，这里有一些相关信息...

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

当将优化调整到11时，Visual C++编译器将其编译为两条机器指令，这两条指令都不是分支。它还优化掉了retvals数组，因此没有缓存失效。

- Jive Dadson

---

那似乎比我问题末尾的那个简单。我很好奇在Visual C++中，它们是否是相同的指令，即static const int res[] {-1, 1, -1}; const int* const m1pow = res + 1; return m1pow[n%2]会产生相同的结果。 - alfC

这是最终的竞争者（请参见我对问题的编辑）。 - alfC

它是如何优化掉retvals数组的？https://godbolt.org/g/cd1JkX显示，MSVC（像其他编译器一样）实际上是从内存中加载静态数组。如果经常使用，您将不会有任何缓存未命中，但这仅因为它将保持在L1d中。 - Peter Cordes

Answer 6

什么情况？

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

n%2 最有可能只会计算一次

更新

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

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

return res[n%2 + 1];

- Severin Pappadeux

---

对于 n=-1，它会得到 3（就像 1 - (1-2*(n%2)) 一样） - alfC

取模运算仍然比掩码运算慢得多... - Flavien Volken

@Alnitak：转换仅适用于非负值的 n（例如无符号类型）。 - R.. GitHub STOP HELPING ICE

问题与原代码中的int n都没有排除n可能是负值，因此这种解决方案是无法使用的。 即使不考虑n可能是负值的情况，在编译器中也很可能无法得出结论并限制优化。建议简单地改为unsigned n;。 - chux - Reinstate Monica

@chux 对的，应该是 n%2u，它应该会产生与 n&1 完全相同的代码。 - David Schwartz

Answer 7

如果我们按顺序执行计算，为什么不分别处理正循环和负循环，完全跳过评估呢？

泰勒级数展开近似自然对数(1+x)是这种类型问题的完美例证。每个项都有(-1)^(n-1)或(1)^(n-1)。没有必要计算这个因子。你可以通过执行每两个项之间的1个循环或者通过执行奇数项和偶数项的两个循环来"切片"解决问题。

当然，由于计算本质上是实数域的倒数，您将使用浮点处理器来评估单个术语。一旦您决定这样做，您应该只使用库实现自然对数。但如果出于某些原因，您决定不使用，那么不浪费周期来计算-1的值到N次方肯定会更快，但差别不大。

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

- Fred Mitchell