在C++中创建一个没有x*x的square()函数

Question

我是自学C++和Bjarne Stroustrup的"Programming-Principles and Practices Using C++"一书.其中一个"试试这个"问:

在不使用乘法运算符的情况下实现square(); 也就是说,通过重复添加来执行x*x(在0处开始变量结果并将x添加到x次).然后使用该square()运行某个版本的"第一个程序".

基本上,我需要创建一个square(int x)函数,它将返回它的平方而不使用乘法运算符.到目前为止我有这个:

int square(int x)
{
    int i = 0;
    for(int counter = 0; counter < x; ++counter)
    {
        i = i + x;
    }

return i;
}

但我想知道是否有更好的方法来做到这一点.上述功能有效,但我非常确定这不是最好的方法.有帮助吗？

Answer 1

在我想到这个想法之前,帕特·彼得森就把这个想法从脑子里偷走了.

#include <iostream>

template <typename T>
T square(T x) {
    if(x < 0) x = T(0)-x;
    T sum{0}, s{x};
    while(s) {
        if(s & 1) sum += x;
        x <<= 1;
        s >>= 1;
    }
    return sum;
}

int main() {
    auto sq = square(80);
    std::cout << sq << "\n";
}

Answer 2

就运行时间复杂度而言，你的实现足够清晰和简单，对于输入n个元素，其运行时间为T(n)=\xce\x98(n)。当然你也可以使用分而治之的方法，假设将n个元素拆分为n/2:n/2，最后递归计算然后将两部分相加，运行时间将类似于\n T(n)=2T(n/2)+\xce\x98(n )=\xce\x98(nlgn)，我们可以发现它的运行时间复杂度比你的实现更差。

\n