## 不使用乘除和pow计算一个数的平方 作者是 在线疯狂 发布于 2015年3月10日 在 算法, 译林.

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

```Examples:

Input: n = 5
Output: 25

Input: 7
Output: 49

Input: n = 12
Output: 144```

``````// 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```

```  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 = 2*x + 1
n2 = (2*x + 1)2 = 4*x2 + 4*x + 1
floor(n/2) 可以通过右移运算实现. 2*x and 4*x 可以通过左移运算实现。```

``````// 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```

Pingbacks已关闭。

1. CollecTheme 发布于 2015年3月11日 13:15 #

经过贵站，留下脚印，诚心盼望回访 www.collectheme.com