JavaScript之二进制数

背景

最近，在练习《剑指offer》里的算法题的过程中，遇到了一个有趣的题目：不用加减乘除做加法

题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

示例：

输入：1，2
输出：3

javascript

1
2
3

function Add(num1, num2) {
    // write code here
}

不用加减乘除做加法？这莫不是先有蛋还是先有鸡的问题！！！

不过稍加思索之后，大家应该也都能想到，计算机存储数据和计算都是使用二进制和位运算符，那解题思路应该就是用两块知识。

可是，平时开发需求的时候，哪有使用到二进制和位运算的。这就触及我的知识盲区了，别问，问就是不会！😂

好了，玩笑归玩笑，接下来就一起来梳理一下二进制数相关的知识。

二进制数

为了实现不同的目的，其实都是为了简化问题，二进制数在计算机中有不同的表示方法，如原码、反码、补码等。

注意：本文为了简化运算，二进制数都是用一个字节（8个二进制位）来简化说明

真值

我们表示自然数包括正数，负数和0，下面是1和-1的二进制表示，我们称为真值

plaintext

1 2	+ 00000001 # +1 - 00000001 # -1

8位二进制数能表示的真值范围是[-2^8, +2^8]

原码

由于计算机只能存储0和1，不能存储正负，所以用8个二进制位的最高位来表示符号，0表示正，1表示负，用后七位来表示真值的绝对值，这种表示方法称为原码表示法，简称原码。

上面的1和-1的原码如下：

plaintext

1 2	0 0000001 # +1 1 0000001 # -1

由于10000000的意思是-0，这个没有意义，所有这个数字被用来表示-128，所有负数就比整数多一个。

由于最高位被用来表示符号了，现在能表示的范围是[-2^7, +2^7-1]，即[-128, +127]

反码

反码是另一种表示数字的方法，其规则是：

整数的反码和其原码一样
负数的反码将其原码的符号位不变，其余各位按位取反

上面的1和-1的反码如下：

plaintext

1 2	0 0000001 # +1 1 1111110 # -1

反码的表示范围是[-2^7, +2^7-1]，即[-128, +127]

补码

补码是另外一种表示方法，主要是为了简化运算，将减法变为加法而发明的数字表示法，其规则是：

整数的补码和原码一样
负数的补码是其反码末尾加1

上面的1和-1的补码如下：

plaintext

1 2	0 0000001 # +1 1 1111111 # -1

补码的表示范围是[-2^7, +2^7-1]，即[-128, +127]

js中的二进制数整数

一名合格的jser应该支持在js中只有一种数字类型，就是浮点型，js的浮点数遵循IEEE 754规范

然而在js中还有另一种类型的数据，那就是用32个比特位表示的整数，只要对js中的任何数字做位运算操作系统内部都会将其转换成整形

js中的这种整形是区分正负数的，我们根据上面的知识推断js中的整数的表示范围是[-2^31, +2^31-1]，即[-2147483648, +2147483647]

原生二进制字面量

es6中引入了原生二进制字面量，二进制数的语法是0b开头，我们将会用到这个新功能，目前chrome最新版已经支持。

plaintext

1 2	0b111 // 7 0b001 // 1

进制转换

Number.prototype.toString：方法的参数可以指定转换的进制

javascript

1 2	(3).toString(2) >> 11

js中的位运算

js中的位运算符有下面这些，对数字进行这些操作时，系统内部都会讲64的浮点数转换成32位的整形

下述运算符在js中的验证方法为：

javascript

1 2	(0b101 & 0b011).toString(2) >> "1"

& 与

与运算符会将操作数和被操作数的相同位进行运算，如果都为1则为1，如果有一个为0则为0

plaintext

| 或

只要有一个为1就是1，两个都为0则为0

plaintext

^ 异或

两个位不同则为1，两个位相同则为0

plaintext

~ 非

如果是1则变为0，如果是0则边为1

plaintext

1
2
3

101
---
010

<< 左移(有符号右移)

左移的规则就是每一位都向左移动一位，末尾补0，其效果相当于×2，其实计算机就是用移位操作来计算乘法的

plaintext

1
2
3

010
---
0100

>> 算数右移(有符号右移)

算数右移也称为有符号右移，也就是移位的时候高位补的是其符号位，整数则补0，负数则补1

javascript

(0b111>>1).toString(2)
>>> "11"

(-0b111>>1).toString(2)
>>> "-100"

负数的结果好像不太对劲，我们来看看是怎么回事

plaintext

-111 // 真值
1 0000111 // 原码
1 1111001 // 补码
1 1111100 // 算数右移
1 0000100 // 移位后的原码
-100 // 移位后的真值

>>> 逻辑右移(无符号右移)

逻辑右移又称为无符号右移，也就是右移的时候高位始终补0

javascript

(0b111>>>1).toString(2)
>>> "11"

(-0b111>>>1).toString(2)
>>> "1111111111111111111111111111100"

问题解析

实现代码：

javascript

function Add(num1, num2) {
    if(num1 === 0) return num2
    if(num2 === 0) return num1
    return Add((num1^num2),(num1&num2) << 1)
}

代码解释：

a^b 相当于无进位求和，比如 1^9=8 （1001 ^ 0001 = 1000），这里的第一位（最右位）如果是正常求和，则 1+1 应该进一位到第二位，但它无视掉了进位的结果。

（a&b）<< 1 相当于求每一位的进位数，比如（1&9）<< 1 = 2 （（1001 & 0001）<< 1 = 0010），刚刚好得到的就是 a^b 过程中被无视掉的那些进位（本例只涉及一处进位）。

所以 add((a^b),(a&b) << 1) 就相当于 (a^b) + (a&b) << 1，将两个数无进位求和结果 + 每一次求和得到的进位。

上述代码就是在不断重复这个过程，直到进位数为0为止，则得到结果。

此外，注意 << 是有符号左移，下面举个例子方便理解。

比如 1 + （-2）求和。
1 ^ （-2）等价于 0001 ^ 1110 = 1111
1 & （-2）<< 1 等价于（0001 & 1110） << 1 = 0
所以当第一次运算结果传入add函数时，因为此时b形参已经等于0，所以返回 1111 即 -1

赶在2020年过完之前发布，这是一份倔强！