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

Question

许多算法需要计算(-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; 表现力很好,但只有优化.

Answer 1

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

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

我只想澄清这个答案的来源.最初的海报alfC在发布许多不同的计算方法方面做得非常出色(-1)^ n有些方法比其他方式更快.
如今处理器的速度和它们一样快,优化编译器就像它们一样好,我们通常会认为可读性超过了从操作中削减一些CPU周期的微小(甚至可以忽略不计)的改进.
有一段时间,一个通过编译器统治地球,MUL操作是新的和颓废的; 在那些日子里,2次操作的力量是无偿优化的邀请.

Answer 2

通常你实际上并没有计算(-1)^n,而是跟踪当前的符号(作为一个数字是-1或者1)并且每次操作都将其翻转(sign = -sign),在处理你n的顺序时执行此操作,你将获得相同的结果.

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

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