整数开平方算法学习记录

        之前同学问我一段代码。本来我也不懂，就去查了一下，又没睡着午觉连想了大概5小时，终于想通了。此文纪念一下那个头脑发热的中午。

        这是那段代码。

        《平方根的C语言实现(二) —— 手算平方根的原理》(https://www.cnblogs.com/Colin-Cai/p/7220506.html)这篇的思想跟我看到的代码的思想是一样的，于是我认真学习了一下。

        计算方法原来从完全平方公式里来的

其实是开方结果的最低位，这一轮计算中要算的； 是开方结果的第2位到最高位，是上一轮计算的结果； 是进制数。

        整个计算过程就是

粗略理解，每2位被开方数可得到1位结果，然后余数就扔给下一轮计算，跟除法一样。两位两位地排是因为平方关系，算立方根当然就是3位3位地排好咯。

十进制就是 。

二进制就是，而且b不是0就是1，不用像十进制那样要比较很多次，也不需要用到乘法。

        二进制计算中 4a 恰好是 a 左移2位，想到这就能理解代码了。下面就看别人代码是怎么通过 root 的移动实现 root 既作根也作 4a 的。

        可以看到，place的作用有：1、标记；2、在  里面，参与比较；3、为 root 赋值。