Why (n>>1) is error?


  • 0
    A
    class Solution {
    public:
        double power(double x, int n) {
            if (n==0) return 1;
            double y = power(x, n>>1);
            if (n%2==0) return y*y;
            else return y*y*x;
        }
        double pow(double x, int n) {
            if (n<0) return 1.0/power(x,-n);
            else return power(x,n);
        }
    };
    

    when input: x=1.0, n=-2147483648
    It can't AC, but if using(n/2) raplace (n>>1), it will get AC, why?


  • 0
    K

    The reason can be explained as follows. power(x, -2147483648 ) will call power(x, -1073741824) which will call power(x, -536870912) which subsequently will call power(x,-1).
    Now -1>>1 will be equal to -1 but -1/2 will be equal to 0. Hence when using n>>1 your recursion will never terminate. It will give you stack overflow error. But in second case you recursion will terminate due to statement if (n==0) return 1; resulting in right answer.

    If you want to know why -1>>1=-1 try to find out bit representation of signed integer and how shift operator work on signed integer.


Log in to reply
 

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