CODEWITHSUNDEEP
c++calgorithmtime-complexity
AlgorithmGeek
AlgorithmGeek

Reputation: 33

Reducing time complexity

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

The above code checks whether a number is power of two. The worst case runtime complexity is O(n). How to optimize the code by reducing the time complexity?

Upvotes: 3

Views: 2599

Answers (5)

rajeev
rajeev

Reputation: 1

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

Upvotes: 0

Lundin
Lundin

Reputation: 215350

Instead of dividing a number by 2, you can right shift it by 1. This is an universal optimizing rule for division by 2,4,8,16,32 and so on. This division can be replaced by right shift 1,2,3,4,5 and so on. They are mathematically equivalent.

Shift is better, because the assembler division instruction is terribly inefficient on most CPU architectures. A logical shift right instruction is executed much faster.

However, the compiler should be able to do this optimization for you, or it has a pretty bad optimizer. Style-wise it may be better to write division and modulo operators in the C code, but verify that the compiler actually optimizes them to shift operations.

Upvotes: 0

Prasoon Saurav
Prasoon Saurav

Reputation: 92942

Try if( n && (n & (n-1)) == 0) temp = 1; to check whether a number is power of two 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 which is power of 2 has only one bit set.

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

Running time O(1) ;-)

As @GMan noticed n needs to be an unsigned integer. Bitwise operation on negative signed integers is implementation defined.

Upvotes: 15

Botz3000
Botz3000

Reputation: 39670

try this: bool isPowerOfTwo = n && !(n & (n - 1));

Upvotes: 1

EboMike
EboMike

Reputation: 77762

How about this?

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

Upvotes: 2

Related Questions