Calculate square of a number without using *, / and pow()

不使用乘除和pow计算一个数的平方 

给定一个整数n，在不使用乘除和pow函数的前提下计算其平方的值。

Examples:

Input: n = 5
Output: 25

Input: 7
Output: 49

Input: n = 12
Output: 144

一个直观的解法是重复地向结果加n。下面是该思路的C++实现。

// Simple solution to calculate square without
// using * and pow()
#include<iostream>
using namespace std;
 
int square(int n)
{
   // handle negative input
   if (n<0) n = -n;
 
   // Initialize result
   int res = n;
 
   // Add n to res n-1 times
   for (int i=1; i<n; i++)
       res += n;
 
   return res;
}

// drive program
int main()
{
    for (int n = 1; n<=5; n++)
        cout << "n = " << n << ", n^2 = "
             << square(n) << endl;
    return 0;
}

Output

n = 1, n^2 = 1
n = 2, n^2 = 4
n = 3, n^2 = 9
n = 4, n^2 = 16
n = 5, n^2 = 25

上述解法的时间复杂度是O(n)。我们使用位运算符可以在O(Logn)的时间内完成。该思路基于下面的事实。

  square(n) = 0 if n == 0
  if n is even 
     square(n) = 4*square(n/2) 
  if n is odd
     square(n) = 4*square(floor(n/2)) + 4*floor(n/2) + 1 

例如

  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++实现。

// Square of a number using bitwise operators
#include<iostream>
using namespace std;
 
int square(int n)
{
    // Base case
    if (n==0) return 0;
 
    // Handle negative number
    if (n < 0) n = -n;
 
    // Get floor(n/2) using right shift
    int x = n>>1;
 
    // If n is odd
    if (n&1)
        return ((square(x)<<2) + (x<<2) + 1);
    else // If n is even
        return (square(x)<<2);
}

// drive program
int main()
{
    for (int n = 1; n<=5; n++)
        cout << "n = " << n << ", n^2 = " << square(n) << endl;
    return 0;
}

Output

n = 1, n^2 = 1
n = 2, n^2 = 4
n = 3, n^2 = 9
n = 4, n^2 = 16
n = 5, n^2 = 25

上述解法的时间复杂度是O(Logn).

原文链接：http://www.geeksforgeeks.org/calculate-square-of-a-number-without-using-and-pow/

本文链接：http://bookshadow.com/weblog/2015/03/10/calculate-square-of-a-number-without-using-and-pow/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码