剑指 Offer 65. 不用加减乘除做加法（加法器解法）
June 27, 2021算法LeetCode
加法器解法
在《编码》（此处强烈推荐，基础不好的同学也可以看）一书中看到使用继电器组装成或、与、非、异或各种门电路，依靠门电路实现加法器，在依靠补码机制实现减法运算。正好遇到此题，借助书中的思想通过 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;
};
知命不惧，日日自新。