题⽬描述
给定⼀个⾮负整数 x，计算并返回 x 的平⽅根，即实现 int sqrt(int x) 函数。
正数的平⽅根有两个，只输出其中的正数平⽅根。如果平⽅根不是整数，输出只保留整数的部分，⼩数部分将被舍去。
示例1 输⼊：8 返回值：2 解释：8 的平⽅根是 2.82842…，由于⼩数部分将被舍去，所以返回 2
思路及解答
暴力枚举
从0开始递增，找到最大的i满足i² ≤ x < (i+1)²
时间复杂度：O(√x)，最多需要√x次循环
空间复杂度：O(1)，只使用常数空间
二分查找（最优解）
在[0, x]范围内查找平方根，不断缩小区间，直到找到满足条件的最大整数
如果 m2 < n, ⽽且 （）（m+1）2>n，那么说明 m 是 n 的平⽅根。
时间复杂度：O(logn)，每次将搜索范围减半
空间复杂度：O(1)
牛顿迭代法
这就属于是使用数学方法了
利用切线逼近平方根，迭代公式：xₙ₊₁ = (xₙ + a/xₙ)/2，其中a是要求平方根的数
时间复杂度：O(log x)，收敛速度极快
空间复杂度：O(1)，常数空间
位运算
利用二进制特性逐位确定平方根，最高位开始，逐位尝试将1变为0或保持1
时间复杂度：O(log x)，固定32次循环（对于int类型）
空间复杂度：O(1)，常数空间
位运算原理解析
为什么从第16位开始？
int最大值：2³¹-1 ≈ 21亿
√21亿 ≈ 46340 < 2¹⁶ = 65536
所以只需要检查16位即可
执行过程示例（x=8，二进制1000）：