炒河粉的无量法师

剑指 Offer 65. 不用加减乘除做加法(加法器解法)

June 27, 2021算法LeetCode

原题:剑指 Offer 65. 不用加减乘除做加法

加法器解法

《编码》(此处强烈推荐,基础不好的同学也可以看)一书中看到使用继电器组装成或、与、非、异或各种门电路,依靠门电路实现加法器,在依靠补码机制实现减法运算。正好遇到此题,借助书中的思想通过 Js 来模拟实现,完成了正负数的加法运算。

无符号二进制加法运算

二进制串从右往左,按位相加,值大于等于二则进位,计算下一位的时候将两个值和进位相加,得出进位,然后依此类推。

// 负责无符号二进制码加法运算
function sum(aStr, bStr) {
  // 两个二进制位长度不等则异常(需要先使用 pad 函数处理)
  if (aStr.length !== bStr.length) {
    throw Error('err');
  }
  function helper(aL, bL) {
    if (aL.length === 0) {
      return ['0', ''];
    }
    const ai = aL.shift();
    const bi = bL.shift();
    const [c, s] = helper(aL, bL);
    const ons = [ai, bi, c].filter(i => i === '1'); // 获取所有的 “1”
    let curCarry = ons.length >= 2 ? '1' : '0'; // 如果有两个及以上 “1” 相加则进位
    let curBit = ons.length % 2; // 三个:“1”,两个:“0”,一个:“1”,零个:“0”
    return [curCarry, curBit + s]; // 参数1:是否进位,参数2:加法后的二进制位
  }
  const [, sumStr] = helper(aStr.split(''), bStr.split(''));
  return sumStr;
}

sum('01', '10');                         // "11"
sum('001', '011');                       // "100"
sum('01111111111111', '01111111111111'); // "11111111111110"

不过以上仅仅是实现了加法运算,那么如何实现减法运算呢?这时候有需要用到补码原理了,计算机中的减法是通过加法来实现的,怎么加呢?

实际上【数1 - 数2】等于【(数1 + 数2的补数)- 数2与补数的和】,其中 “数2与补数的和“ 就是当前数值表示范围的上限,因为有了它我们加出来的值会溢出,而溢出的高位正好是我们要减去的值。为了简单起见,我们使用三个 bit 表示一个数,然后举几个例子(下面十进制中 8 和二进制的 1000 表示上限范围):

2 - 1 = 2 + (8 - 1) - 8 = 1
"010" - "001" = "010" + ("1000" - "001") - "1000" = "001"

以上便是无符号二进制减法运算,在有符号二进制中 2 - 1 其实等于 2 + (-1),而 -1 则表示为 1 的补数(8 - 1)。我们用 3 位二进制表示正负数排列如下:

0,1,2,3,-4,-3,-2,-1

为何这样排列?比如上面 2 - 3 等于 2 + (-3),也等同于 -3 的位置往右两位结果为 -1。比如计算 2 - 1 等于 2 + (-1),等同于 -1 位置往右两位,但此时右边没有了,这个就溢出从左开始,第一步到 0 第二步到 1,所以计算结果为 1

有了加减法,那么乘法呢?比如 2 * 3 等于 2 + 2 + 2,通过循环的方式加上去就实现乘法啦。可能你看到这里依旧隐隐约约明白,但是又没完全明白,推荐你去看《编码》原书。

序列化与反序列化二进制码串

首先介绍第一个工具函数,此函数用于将串长度对齐,正数和零高位填充 “0“,负数在高位填充 “1。

// 负责填充二进制码(可指定填充 “1” 还是 “0”)
function pad(str, sym) {
  return str.padStart(64, sym); // 此处的 64 表示生成指定位长的二进制串,超过则溢出
}

pad('101001', '0'); // 0000000000000000000000000000000000000000000000000000000000101001
pad('101001', '1'); // 1111111111111111111111111111111111111111111111111111111111101001

第二个工具函数,用于计算反码,即将 “0“ 变为 “1“,将 “1“ 变为 “0“。

// 负责翻转二进制码
function turnBinary(str) {
  return str.split('').map(i => i === '0' ? '1' : '0').join('');
}

turnBinary('0101010101'); // 1010101010

序列化二进制串

// 负责将一个数序列化位有符号二进制位
function binaryStringify(num) {
  let valueStr;
  if (num < 0) {
    valueStr = num.toString(2).replace(/^-/, ''); // 去除前戳 “-”
    // 原码 -> 补码:
    valueStr = turnBinary(valueStr);         // 获取反码
    valueStr = pad(valueStr, '1');           // 填充二进制位(由于是负数,所以往左边填充 “1”)
    valueStr = '1' + valueStr.substr(1);     // 确保第一位符号位为 “1”
    valueStr = sum(valueStr, pad('1', '0')); // 加上 “1” 得出补码
  } else {
    valueStr = num.toString(2);
    valueStr = pad(valueStr, '0');
  }
  return valueStr;
}

binaryStringify(1); // 0000000000000000000000000000000000000000000000000000000000000001
binaryStringify(-2); // 1111111111111111111111111111111111111111111111111111111111111110

反序列化二进制串

// 负责将有符号二进制位解析为数值
function binaryParse(str) {
  const l = str.split('');
  if (l[0] === '0') {
    return parseInt(l.join(''), 2);
  }
  l.shift(); // 移除符号位
  // 补码 -> 原码:
  let valueStr = sum(pad(l.join('')), binaryStringify(-1)); // 先减一(由于不能直接使用 “-”,通过加法 -1 来实现)
  valueStr = turnBinary(l.join(''));               // 获取反码
  return parseInt(`-${valueStr}`, 2) - 1;          // 通过 parseInt 转换出数值
}

binaryParse('0000000000000000000000000000000000000000000000000000000000000001'); // 1
binaryParse('1111111111111111111111111111111111111111111111111111111111111110'); // -1

完成有符号加法运算

将 a 和 b 两个值序列化为二进制串,使用加法器相加,将结果反序列化为数值返回。

// 加法方法(支持正负数)
var add = function(a, b) {
  var aStr = binaryStringify(a);
  var bStr = binaryStringify(b);
  const res = sum(aStr, bStr);
  return binaryParse(res);
};

现已将代码分享到 LeetCode 提解:通过加法器的解法(不用位运算)

其他解法

位运算解法

高赞解法:不用加减乘除做加法(位运算,清晰图解)

var add = function(a, b) {
  let n = a ^ b;
  let c = (a & b) << 1;
  while (c != 0) {
    a = n;
    b = c;
    n = a ^ b;
    c = (a & b) << 1
  }
  return n;
};

毁天灭地解法

【前方高能】JavaScript不用任何算术运算符,位运算符或Math对象实现整数加法

当时没仔细看代码实现,直接粘贴跑了一下本地执行没问题,往上提交没通过内存直接跑满崩了,定睛一看,我的妈呀大佬的脑回路果然不一样,操作挺骚,不保证能通过。

佛系解法

为什么不用?

var add = function(a, b) {
    return a + b;
};

野生程序猿,专业铲屎官。#Github 账号