```
class Solution {
public:
int mySqrt(int x) {
int right=1, temp=x;
while (temp >0){
temp >>= 2;
right <<= 1;
}
int left= right>>1;
while (left < right-1){
int mid = (left+right)/2;
int c= mid*mid;
if (c/mid != mid || c > x) right = mid;
else if (c < x) left = mid;
else return mid;
}
return left;
}
};
```