求一个数的平方

Question

我发现了这个问题，

编写一个函数 returns 给定整数 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。

求一个数的平方

Finding square of a number

bit-manipulation

bit

bitwise-operators