降低时间复杂度

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）。如何通过降低时间复杂性来优化代码？

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需求是一个无符号整数。负符号整数的按位运算是实现定义的。

Answer 2

这个怎么样？

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

Answer 3

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

Answer 4

而不是分割数2，你可以通过右转向1.它这是2,4,8,16,32除法的普遍优化规则和等等。这种划分可以由右移1,2,3,4,5等替代。它们在数学上相当。

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

但是，编译器应该能够为你做这个优化，或者它有一个非常糟糕的优化器。从风格上看，在C代码中编写除法和模运算符可能会更好，但要验证编译器是否实际优化了它们以转移操作。

Answer 5

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