c++ - Reducing time complexity -

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

the above code checks whether number power of two. worst case runtime complexity o(n). how optimize code reducing time complexity?

try if( n && (n & (n-1)) == 0) temp = 1; check whether number power of 2 or not.

for example :

n = 16;

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

a number power of 2 has 1 bit set.

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

running time o(1) ;-)

as @gman noticed n needs unsigned integer. bitwise operation on negative signed integers implementation defined.