使用按位运算符求数字的平方[关闭]

Question

无需使用乘法、除法或幂函数即可计算数字的平方。

int calculateSquare(int num)
{   
    if(num == 0) return 0;


    if(num < 0) num = -num;

    int x = num >> 1;

    if(num & 1)
      return((calculateSquare(x) << 2) + (x << 2) + 1 );
    else
      return(calculateSquare(x) << 2);
}

我无法理解代码的意思，所以我想帮助解释代码。

如果可以的话请一步步清楚地阐述一下代码的递归部分。

简而言之，问题与位操作相关。

Answer 1

你可以尝试重现学校乘法算法：

10 * 10 = 1010b * 1010b =

    1010
    1010
    ----
   1010
 1010
 -------
 1100100

我们应该检查位

i

是否已设置，将

num << i

添加到

result

。

代码：

int calculateSquare(int num) {
  if (num < 0)
    num = -num;

  int result = 0;

  for (int i = 0; i < 31; ++i)
    if ((num & (1 << i)) != 0) /* if i-th bit is set */
       num += (num << i);      /* add num * 2 ^ i    */

  return result;
}