c++ - 降低时间复杂度

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

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

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 的幂数只设置了一位。

n & (n - 1) unsets the rightmost set bit .

运行时间 O(1) ;-)

作为@GMan注意 n 需要是一个无符号整数。负符号整数的按位运算是实现定义的。