# Why (n>>1) is error?

• ``````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?

• 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.

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