What's the difference between "return (int)Math.pow(2, leftH + 1) - 1" and "return (2<<leftH)-1;"


  • 0
    S

    The code as following:

    public int countNodes(TreeNode root) {
    if (root == null)
    return 0;

        int leftH = getLiftHigh(root);
        int rightH = getRightHigh(root);
        
        if(leftH == rightH){
             return (int)Math.pow(2, leftH + 1) - 1;
            //return (2<<leftH)-1;
        }
        else
          return countNodes(root.left) +  countNodes(root.right) + 1;
    }
    
    public int getLiftHigh(TreeNode n){
        if (n == null) return 0;
        
        int height = 0;
        while(n.left != null){
            height++;
            n = n.left;
        }
        return height;
    }
    
    public int getRightHigh(TreeNode n){
      if(n==null) return 0;
    
      int height=0;
      while(n.right!=null){
        height++;
        n = n.right;
      }
      return height;
    }
    

    When return "(int)Math.pow(2, leftH + 1) - 1", there is a TLE, but if return "return (2<<leftH)-1;", it would be Ok. What is the difference between "return (int)Math.pow(2, leftH + 1) - 1" and "return (2<<leftH)-1;"?


  • 0

    Calling a function costs time. And pow supports other bases, so it will look at the given base, decide what to do and how to do it, and eventually somehow do it. That's a lot more effort than the simple bit shift that 2<<leftH is. Hence the latter is faster.


  • 0
    S

    Thank you for your reply. It's helpful.


  • 1
    A

    As StefanPochmann mentioned, bit shifting is faster than calling a method when you are multiplying or dividing a number by a power of two. There are a few reasons for this.

    The main reason is that most modern processors implement bit shifting using a barrel shifter which allows shifting an operand a variable distance in a single clock cycle.

    Another reason is that the java.lang.Math.pow(double, double) function, as the method signature indicates, takes in double precision floating point values and not integer values. You are calling it with integer parameters, but those are implicitly converted to double values by the compiler. Floating point arithmetic is very slow compared to integer arithmetic and especially compared to bit operations which typically complete in one clock cycle.

    There is also a slight overhead caused by calling a method which will have to push the current method state onto the system stack, jump to the correct location in memory, and then once it is finished with that, it has to restore state by popping the method state off the stack and returning to the address which was in the program counter before jumping to the new address.

    But again the main reason is just that the bit shifting operation is implemented directly in hardware and if it is implemented as a barrel shifter, it will complete in one clock cycle, but even if it is just a shift register, it will still only take a few clock cycles to complete. This is still much faster than the hundreds or possibly thousands of clock cycles that it takes to invoke the method, execute it, and return.

    If you want, you can check out the implementation of the java.lang.StrictMath.pow(double, double) function, which is invoked from the java.lang.Math.pow(double, double) function here ( http://developer.classpath.org/doc/java/lang/StrictMath-source.html ). As of the time of this writing, the function definition starts on line 1511. I would have copied it here, but the implementation is around 160 lines.


  • 0

    Thanks, nice extra explanations. Also thanks for the link (can btw go directly to line 1511).


  • 0
    S

    Thank you so much! It helps me a lot!


Log in to reply
 

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