IsPowerOfTwo. How come this solution is faster than bit-wise operation solution?


  • 3
    K

    I submitted two solutions to powerOfTwo problem.

    First:

    bool isPowerOfTwo(int n) {
            if(n == 0)              return false;
            if(n == 2 || n == 1)    return true;
            if(n%2 != 0)            return false;
            else                    return isPowerOfTwo(n>>1);
        }
    

    Second:

    bool isPowerOfTwo(int n) {
            if(n <= 0)              return false;
            else                    return !(n & (n-1));
        }
    

    How come the first solution has a runtime of 4ms and the second one has 8ms?

    The first solution is recursive, has two division operations in each recursive call. It should be way slower than just a bit operation.


  • 0
    A

    When I translate the second solution from c++ to c , the runtime is 4ms.


  • 0
    K

    This would've been suitable as a comment.


  • 0
    J

    but still, somebody got 4ms in C++, how is the measurement done?


  • 0
    E

    I think the time measurement is not accurate when the running time is very short. I got both of the methods 8ms using C++.

    Sometimes for some problems, you got different running time for the same code submitted several times.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.