Reducing time complexity

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

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?

The runtime complexity of your code at worst is O(log n) still you can do better (O(1)) as is shown below — CashCow, Jan 25 '11 at 10:12

score 15 · Accepted Answer · edited May 23 '17 at 12:10

15

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.

edited May 23 '17 at 12:10

Community

1
1

answered Jan 25 '11 at 09:57

Prasoon Saurav

91,295
49
239
345

3

Nice little diagram. Of course, `n` needs to be `unsigned` to guarantee this works. – GManNickG Jan 25 '11 at 10:03
1

if it isn't, changing the `n` to `n > 0` does the job. – etarion Jan 25 '11 at 10:06

score 2 · Answer 2 · answered Jan 25 '11 at 09:58

2

How about this?

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

answered Jan 25 '11 at 09:58

EboMike

76,846
14
164
167

score 1 · Answer 3 · answered Jan 25 '11 at 09:59

1

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

answered Jan 25 '11 at 09:59

Botz3000

39,020
8
103
127

score 0 · Answer 4 · edited Oct 16 '14 at 06:51

0

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

edited Oct 16 '14 at 06:51

Stephan

4,187
1
21
33

answered Oct 16 '14 at 06:29

rajeev

1

score 0 · Answer 5 · answered Jan 25 '11 at 11:05

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.

Reducing time complexity

5 Answers5