减少时间复杂度

Question

int main()
{
   int n ;
   std::cin >> n; // or scanf ("%d", &n);
   int temp;
   if( n ==1 ) temp = 1; // if n is 1 number is power of 2 so temp = 1
   if( n % 2 != 0 && n!= 1) temp =0; // if n is odd it can't be power of two
   else
   {
       for (;n && n%2 == 0; n /= 2);
       if(n  > 0 && n!= 1) temp = 0; // if the loop breaks out because of the second condition
       else temp = 1;
   }

   std::cout << temp; // or printf ("%d", temp);
}

以上代码检查一个数是否是2的幂。最坏情况下的运行时间复杂度为O(n)。如何通过降低时间复杂度来优化代码？

- AlgorithmGeek

---

你的代码在最坏情况下的运行时间复杂度为O(log n)，但是你可以做得更好（O(1)），如下所示。 - CashCow

Answer 1

尝试使用 if( n && (n & (n-1)) == 0) temp = 1; 来检查一个数字是否为2的幂次方。

例如:

n = 16;

  1 0 0 0 0 (n)
& 0 1 1 1 1 (n - 1)
  _________
  0 0 0 0 0 (yes)

一个数是 2 的幂次方，只有一个二进制位是 1。

n & (n - 1) 可以将最右边的 1 置为 0，详情请参考此处。

时间复杂度为 O(1) ;-)

正如@GMan指出的那样，n 需要是无符号整数。对负数进行按位运算依赖于实现，其行为的定义因平台而异。

- Prasoon Saurav

---

不错的小图示。当然，为保证其有效性，“n”需要被声明为“unsigned”。 - GManNickG

如果不是这样的话，将 n 改为 n > 0 就可以完成任务。 - etarion

Answer 2

这个怎么样？

bool IsPowerOfTwo(int value)
{
    return (value && ((value & (value-1)) == 0);
}

- EboMike

Answer 3

尝试这个：bool isPowerOfTwo = n && !(n & (n - 1));

- Botz3000

Answer 4

bool ifpower(int n)
{
    if(log2(n)==ceil(log2(n))) return true;
    else return false;
}

- rajeev

Answer 5

不要将一个数字除以2，而是将其右移1位。这是一种通用的优化规则，适用于2、4、8、16、32等除以2的情况。这种除法可以被右移1、2、3、4、5等替代。它们在数学上是等价的。

移位更好，因为大多数CPU架构上的汇编除法指令效率非常低下。逻辑右移指令执行速度要快得多。

然而，编译器应该能够为您执行此优化，否则它的优化器就很糟糕。从风格上讲，在C代码中编写除法和模运算符可能更好，但请验证编译器是否实际将它们优化为移位操作。

- Lundin