Newton method

```
int mySqrt(int x)
{
long g = x;
while(g*g > x)
g = (g + x/g) / 2;
return g;
}
```

Bit manipulation

```
int mySqrt(int x)
{
if(x == 0 || x == 1)
return x;
int h = 0;
while((long)(1 << h) * (long)(1 << h) <= x)
h++;
h--;
int d = h - 1;
int res = (1 << h);
while(d >= 0)
{
if((long)(res | 1 << d)*(long)(res | 1 << d) <= x)
res |= (1 << d);
d--;
}
return res;
}
```