找到一个数字的平方

Question

我发现了这个问题,

编写一个函数,返回给定整数n的平方而不使用乘法.

对此的解决方案是

public static int sq(int n){
        int i = n;
        int sq = 0;
        int count = 0;

        while(i > 0){
            if((i & 1) == 1){
                sq += n << count;
            }

            i = i >> 1;
            count++;
        }

        return sq;
    }

我理解这个函数在做什么,但我不明白为什么这个有用.

谁能解释为什么这是一个有效的解决方案？

Answer 1

因为乘法分配超过加法.这可能听起来很神秘,但这才是真正的原因.考虑这个乘法:

100 * 111

显然,只有111左移了两个:11100

这段代码为1 in中的每个位执行此操作i,并对结果求和.因此,原来例如111 * 111成

001 * 111 = 00111
010 * 111 = 01110
100 * 111 = 11100
            -----  +
           110001

允许以这种方式拆分乘法,因为乘法分配超过加法,即001 * 111 + 010 * 111 + 100 * 111等于(001 + 010 + 100) * 111,现在它显然等于111 * 111.