bit-manipulation - 求一个数的平方

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

此代码对 i 中为 1 的每个位都执行此操作，并总结结果。所以它变成了例如 111 * 111进入

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

允许以这种方式拆分乘法，因为乘法分布于加法之上，这就是 001 * 111 + 010 * 111 + 100 * 111等于 (001 + 010 + 100) * 111 ，现在显然等于 111 * 111 .