在科学运算、图形学、游戏等很多领域中，开方是很常见却又非常耗时的运算，因此必须使用快速（有时还要求准确）的开方算法。

说起开方算法我们一般想到的是牛顿迭代法，这里我介绍一种更好的方法——逐比特确认法。

逐比特确认法从数字的本质出发，关注结果的每一比特位。它从最高位开始，向低位逐一确认某位是0还是1。在数字很大时这种方法的速度比牛顿法快不少。

要理解这种方法，得先了解二进制乘法。例如，对于数字10（二进制为0b1010），平方为100（二进制为1100100），它的二进制平方运算过程为：

开方则需要我们反过来，已经有结果N = 1100100，判断根sqrt的二进制：

首先1100100有8位，可以判断sqrt起码有4位且不超过4位。如果sqrt有5位，那么仅最高位10000*10000 = 1 0000 0000就已经大于N；如果sqrt只有3位，即使sqrt为111结果110001也不超过6位。

现在判断sqrt的第4位：如果第4位为1 , sqrt平方运算中有上面（*1）这项

结果 n4 1100100 (N)

结果n43 > N，所以这一位不是1，只能是0。

到目前为止其实都是二分法的思路，先是2^3，然后是2^3 – (2^3 + 2^2)，这样逐次将范围减半。

但是这里有个问题，后面每次都求了sqrt的平方，其实重复求了之前求过的一部分，例如在第二步中，我们算了 1000x1000(*1)，这其实就是第一步中的算的。如果我们每次算完平方，确认了这一位为1后，就从N中减去这一部分的平方，那么下次比较大小的时候就可以少算这一位。

我们从第二步重新开始:

我们第一步确认了1000, 从N中减去它的平方 N = 1100100 - n4，结果为N = 1000100。如果第3位为1, 那么sqrt = 1100, 已确认的为1000, 正在确认的为100, 平方为: