使用移位计算平方

原文链接: 使用移位计算平方

上一篇: atom Windows10 安装 配置c++环境

下一篇: 二分查找

重复使用加法的复杂度是O(n)。我们使用位运算符可以在O(Logn)的时间内完成。

一个数的平方可以转化为 如下的递归格式

 square(6) = 4*square(3)
  square(3) = 4*(square(1)) + 4*1 + 1 = 9
  square(7) = 4*square(3) + 4*3 + 1 = 4*9 + 4*3 + 1 = 49

如果n是偶数，可以写作：
  n = 2*x 
  n2 = (2*x)2 = 4*x2
如果n是奇数，可以写作：
  n = 2*x + 1
  n2 = (2*x + 1)2 = 4*x2 + 4*x + 1
floor(n/2) 可以通过右移运算实现. 2*x and 4*x 可以通过左移运算实现。

c++

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;

// 返回 n^2
int square(int n){
    if (n < 0)
        n = -n;
    if (n == 0)
        return 0;
    int x = n >> 1;
    return (n & 1) ?
           ( (square(x) << 2) + (x << 2) + 1) : //奇数
           (square(x) << 2);//偶数

}
int main(){
    for (int i = -10; i < 10; i++){
        printf("%4d %4d\n", i, square(i) );
    }
    return 0;
}