别人家的面试题：不用加减乘除，求整数的7倍

这是今天早晨来公司无意中听到的题目，据说是某部门 C++ 工程师的面试题。作为爱思考的小前端，听到了也不免会想如果是自己遇到这样一道面试题该怎样做。

这道题目的第一感，相信很多同学都和我想得一样 ---- 和二进制有关。但是，我们知道二进制的操作最方便计算的是 2 次幂的倍数，比如 8 倍，不考虑大数溢出的话，就只要将该整数左移三位就可以了，对应的代码就是：

let multiply8 = (num) => num << 3;

    multiply8(7); //56

你看，8 倍很容易实现，但是 7 倍该怎么做呢？理论上可以先将该数扩大 8 倍，然后再减去自己。可是，题目又限制了不允许使用加减乘除，那么怎么办呢？有兴趣的同学可以思考 5 分钟，再往下看。

不用加号的二进制整数加减法

这道题的关键在于不能使用运算符号，那么一个直接的思路就是能不能不用加减乘除实现整数的加减法呢？其实不难，复习一下大学课本里面计算机组成原理，应该能想起来如何实现基本的加减乘除法。这里，我们其实只需要实现一个基本的加法：

a b a + b 进位

0 0 0 无

0 1 1 无

1 0 1 无

1 1 0 有

从上面的表可以看出一种实现简单的多位二进制整数加法的算法如下：

m 和 n 是两个二进制整数，求 m + n：

1. 用与运算求 m 和 n 共同为 "1" 的位： m' = m & n
2. 用异或运算求 m 和 n 其中一个为 "1" 的位： n' = m ^ n
3. 如果 m' 不为 0，那么将 m' 左移一位（进位），记 m = m' << 1，记 n = n'，跳回到步骤 1
4. 如果 m' 为 0，那么 n' 就是我们要求的结果。

把上面的算法翻译成 JavaScript ：

function bitAdd(m, n){
        while(m){
            [m, n] = [(m & n) << 1, m ^ n];
        }
        return n;
    }

    bitAdd(45, 55); //100

以上，我们就得到了一个自己实现的整数加法，于是我们可以：

function multiply7(num){
        let sum = 0;
        for(var i = 0; i < 7; i++){
            sum = bitAdd(sum, num);
        }
        return sum;
    }

    multiply7(7); //49

这样我们得到了想要的结果，不过如果要改进的话，我们其实可以不需要用循环加法来实现整数乘法，回到前面讨论过的，我们可以先将 num 乘以 8，然后再减去 num，或者说 bitAdd(-num)。

所以我们可以这么做：

let multiply7 = (num) => bitAdd(num << 3, -num);

    multiply7(7); //49

有同学说，负数符号也是减号"-"，能不能不使用？当然可以，因为我们可以利用"补码"：

let multiply7 = (num) => bitAdd(num << 3, bitAdd(~num, 1));

    multiply7(7); //49

好了，到这里，似乎我们得到了一个很完美的解法，不过呢，从数学上，我们还是可以"吹毛求疵"一下：因为在前面的算法里面，我们循环迭代 m 和 n，那么我们的循环什么时候能停下来呢？或者说，这个算法的时间复杂度是多少？

要解决这个问题也很简单，我们简单思考一下，就可以得出，每次迭代的时候，m 末尾连续的 0 一定会至少增加 1 位（因为 & 操作不可能减少 m 末尾的 0，而 1 位左移操作至少会增加 1 个末尾的 0）。当 m 末尾连续的 0 的数量超过 n 的二进制位数之后， m & n 就是 0，此时循环就会结束。因此，这个算法的最坏情况下，循环次数是 log(n)，时间复杂度小于等于 O(log(n))。

其他解法？

上面我们用自己实现的加法解决了这个算法面试题，那么有没有别的什么做法呢？当然也是有的，比如我们可以直接用循环和位操作实现二进制乘法，或者不实现加法，改为实现二进制减法，甚至利用 JavaScript 语言特性用一些投机取巧的方法，比如下面的做法就不违反题意：

let multiply7 = (num) => 
        new Function(["return ",num,String.fromCharCode(42),"7"].join(""))();

    multiply7(7); //49

总之，有各种解法可以玩，多思考总是好的。作为前端，对这样的题目也可以讨论许多方法，有许多思路可以学习。所以，写 C++ 的同学，也要加油，至少别被这样的面试题给难倒。好歹是写 C++ 的，别在算法上输给我大前端