JS位运算/hack/进制转换的特殊用法-不用加减乘除运算符求整数7倍

[noctiomg]

本文主要探讨一道面试题：

使用JS语言，不用加减乘除运算符，求整数的7倍

题目来源：
十年踪迹的博客《别人家的面试题：不用加减乘除，求整数的7倍》

思考

当需要进行避免使用加减乘除的数学运算的时候，通常的方法有：位运算、Eval/Function 传参 hack、进制转换配合字符串转换操作等等，我们参考题目来源中提到的几种方式以及其他大佬们提供的解法来看下这道题。

位运算加法 - 连续7次相加

首先贴出位运算加法常见的做法（此段大量引用自原文）：

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

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' 就是我们要求的结果。

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

bitAdd(45, 55); //100

既然实现了加法，我们就可以很容易地将“乘7”这个操作通过循环加法实现出来：

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

multiply7(7); //49

这里变量 i 自增的时候用了加号，我们用数组将它代替掉：

function multiply7(num){
    let sum = 0;
  	let counter = new Array(7); // 得到 [empty × 7]
    while(counter.length){
      sum = bitAdd(sum, num);
      counter.shift();
    }
    return sum;
}

multiply7(7); //49

位运算加法 8+(-1)

既然有加法，我们也可以用 “目标数的8倍减去目标数的1倍” 来实现 “乘7” 的目的。首先贴出位运算加法常见的做法（此段完全引用自原文）：

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

避免使用负号（减号），我们用补码来代替 ( num * -1) 的操作：

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

黑科技 hack 手段

在 JavaScript 语言里，还有很多黑科技手段，比如我们可以使用字节码的形式来代替 “ * ” 乘号。

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

let multiply7_2 = (num) => 
		eval([num,String.fromCharCode(42),"7"].join(""));

setTimeout(["window.multiply7_3=(num)=>(7",String.fromCharCode(42),"num)"].join(""))

multiply7_1(7);// 49
multiply7_2(7);// 49
multiply7_3(7);// 49

进制转换

参考位运算我们进行一下思考：二进制整数向左位移一位、末尾补0，可以得到其2倍值；十进制整数向左位移一位、末尾补0，可以得到其10倍值；那么我们也可以依此法来进行七进制整数进位补0，来得到7倍值！

let multiply7_4 = 
    (num)=>parseInt([num.toString(7),'0'].join(''),7);

multiply7_4(7);// 49

感悟

题目本身并没有进行非常强的要求，但是我们可以通过一个题目延展成若干个知识点：

• 位运算
• 补码
• 字节码
• 函数构造器 constructor
• eval 方法
• setTimeout 方法
• toString 和 parseInt 在进制操作上的方法

相似的，类似的从使用方式上做限制的题目也可以用这种方法进行处理解答。

不算完整的答案

可以使用三类方式：位运算加法、JS hack、进制转换。实现方式分别如下：

/* -- 位运算 -- */

// 先定义位运算加法
function bitAdd(m, n){
    while(m){
        [m, n] = [(m & n) << 1, m ^ n];
    }
    return n;
}

// 位运算实现方式 1 - 循环累加7次
let multiply7_bo_1 = (num)=>
{
  let sum = 0,counter = new Array(7); // 得到 [empty × 7]
  while(counter.length){
    sum = bitAdd(sum, num);
    counter.shift();
  }
  return sum;
}

// 位运算实现方式 2 - 二进制进3位(乘以8)后，加自己的补码(乘以-1)
let multiply7_bo_2 = (num) => bitAdd(num << 3, -num) ;

/* -- JS hack -- */

// hack 方式 1 - 利用 Function 的构造器 & 乘号的字节码
let multiply7_hack_1 = (num) => 
    new Function(["return ",num,String.fromCharCode(42),"7"].join(""))();

// hack 方式 2 - 利用 eval 执行器 & 乘号的字节码
let multiply7_hack_2 = (num) => 
		eval([num,String.fromCharCode(42),"7"].join(""));

// hack 方式 3 - 利用 SetTimeout 的参数 & 乘号的字节码
setTimeout(["window.multiply7_hack_3=(num)=>(7",String.fromCharCode(42),"num)"].join(""))

/* -- 进制转换 -- */

// 进制转换方式 - 利用 toString 转为七进制整数；然后末尾补0(左移一位)后通过 parseInt 转回十进制
let multiply7_base7 = 
    (num)=>parseInt([num.toString(7),'0'].join(''),7);

其他讨论

大家还可以去原题目的其他转载地址，看看底部讨论区是用怎样的方式处理了这道题~

http://www.360doc.com/content/16/1021/09/10920618_600141167.shtml
https://75team.com/post/multiply7.html