tdzl1.3.cpp

高效整数开平方 我能实现的最高效率的函数

/*------------------------------------------------------------------------------
1.3 编程题：（20分）
写出以你所可能实现的最高效率的函数，用于将一个unsigned int数开平方。如果被求的数
不是完全平方数，求出它的平方根的整数部分。尽你所可能的优化它的效率，并用文字证
明你优化策略有效。
函数的声明为：
unsigned short work(unsigned int n);


天地之灵 20:14:35
巧妙运用二进制上的特征，以及合并运算，可以省略掉乘法和除法
天地之灵 20:15:21
首先，与其理解为二分查找，还不如理解为，在二进制层面上，从前向后决定每一个二进制位上是0还是1
天地之灵 20:16:06
因此，我们可以从最高位向最低位，依次上1，看乘积结果是否大于目标数，如果大于目标数了，那一位就保留0
天地之灵 20:17:24
这样的情况下，我们上1就不用真的去计算乘法，而是将之前的结果，加上上1以前的数左移1所在位置那么多位的两倍（相当于多左移一位），再加上上1的位置左移上1的位置
wtthappy 20:17:52
消化一下
天地之灵 20:17:57
好
wtthappy 20:19:59
最后一段不太明白什么意思？
天地之灵 20:20:55
        11000000
        11000000
________________
1001000000000000
天地之灵 20:22:02
        11100000
        11100000
________________
1001000000000000
0011000000000000
0000010000000000
----------------
1100010000000000
天地之灵 20:22:58
第一行是增加一个1之前乘的结果，第二行是增加1之前的数，左移1所在位+1的结果（也就是左移6位）
第三行是1所在位，再左移所在位的结果
天地之灵 20:23:20
和平方公式(a+b)^2 = a^2+a*b*2+ b^2
天地之灵 20:23:48
a = 11000000
b = 00100000
*2相当于多左移一位
天地之灵 20:27:11


------------------------------------------------------------------------------*/

unsigned short work( unsigned int n )
{
         unsigned int ans = 0;
         unsigned int square = 0;
         unsigned short r = 0;
         for ( int i = 7; i >= 0; --i )
         {
             unsigned int tmp = square;
             tmp += (ans<<(i+1))+(1<<(i<<1));
             if ( tmp <= n )
             {
                  square = tmp;
                  ans |= 1<<i;
             }
         }
         r |= ans;
         return r;
}