今日做一面试题目，写一平方根squareroot函数，函数接口为：

unsigned int squareroot(unsigned int input);　　　　//不考虑float情况

 

经过思考，用位移的方法，一个整数32bits，那么平方根最多16bits，那么对于这16个bits，从最大权重的bit开始，看是置1还是置0，一步一步往后走，到最后一个bit被置完之后，平方根也就求出了。

那么如何判断后16bits中，某一个特定的bit是0还是1呢？

这样判断，因为从most significant到least significant，那么首先将当前需要判断的bit置1，然后平方，看比input是否大，如果置1了都不比input大，那么说明还需要右面的（less significant）bits们帮忙来接近平方根。简单说一句，先将该位置1，平方，如果小于等于input，那么该位就需要置1；否则，置0。

 

那么接下来，就是见证代码的时刻：

#include 
     
      using namespace std; typedef unsigned int uint; uint squareroot(uint input);int main(){    uint input;    cout<<"Plz input a int to be squarerooted:"<
      
       >input;    uint answer = squareroot(input);    cout<<"The answer is:"<
       
        <
       
      
     

 

 

 

中途曾经出过一个问题，问题发生于squareroot()函数中的第7行：

if ( ((answer + (1<<i)) * (answer + (1<<i))) <= input )

一开始对于其中的 (1<<i)部分没有加括号，结果导致结果不对，后来经过仔细排查，发现是运算符优先级的问题，如果不加括号，那么该行为：

if ( ((answer + 1<<i) * (answer + 1<<i)) <= input )

问题是：answer + 1<<i 变成了 (answer + 1)<<i，这肯定不是我们想要的结果。我们想让 1<<i 先结合。

解决方法是：answer + (1<<i)，把括号加上了就ok了。