JS 二进制详解

binary

我们代码中用到的数字、字符串、图片、音视频等等最终都是转换成二进制存储的，而音视频流传输的数据直接是二进制，二进制是必备知识点。

注：右上角带 * 的内容是重点/难点，可能需要多耗时学习消化

一、进制转换

据说人类有十根手指所以常用十进制表示数。

约定如何表示各进制数:

D 表示十进制，Decimal，如 29D
B 表示二进制，Binary，如 11.011B
O 表示八进制，Octal，如 1727O
X 表示十六进制，Hex，如 AD19FX

转十进制

其它进制转十进制，每一位都遵循同样的转换规则：

value * N^M

N – 表示进制，如二进制为 2，十进制为 10
M – 小数点往左依次为 0 1 2 3 4 5 … ，小数点往右依次为 -1 -2 -3 -4 -5 …
value – 表示数值，范围是 [ 0 , N – 1]

// 11010011B => ?D
  1*2^7 + 1*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 1*2^0
= 1*128 + 1*64 + 0*32 + 1*16 + 0*8 + 0*4 + 1*2 + 1*1 
= 211D

// 7135O => ?D
  7*8^3 + 1*8^2 + 3*8^1 + 5*8^0
= 7*512 + 1*64 + 3*8 + 5
= 3677D

// 7FAX => ?D
  7*16^2 + 15*16^1 + 10*16^0
= 7*256 + 15*16 + 10
= 2042D

十进制转二进制

整数位

一直除以 2 直到不够除。

376D 转换过程

除 2        余数
2 | 376
2 | 188
2 |  94
2 |  47  
2 |  23  ... 1
2 |  11  ... 1
2 |   5  ... 1
2 |   2  ... 1
2 |   1
      0  ... 1

补全余数为 0，下方余数为高位，由下往上为 101111000D，转化二进制完毕

小数位

一直乘 2 ，进位记 1 否则记 0，直到消掉小数，或者无尽（一般可通过找到循环来判断）

0.275D 转换过程

           标记   
    0.275
* 2
    0.55    0
* 2  
    0.1	    1 <- 0.1 这个标记点之后用到
* 2     
    0.2	    0 <- 0.2 这个标记点之后用到
* 2     
    0.4     0 * ↓ 
* 2     
    0.8	    0
* 2     
    0.6     1
* 2     
    0.2     1
* 2     
    0.4     0 * ↑  0011 开始循环
* 2     
    0.8     0
* 2     
    0.6     1
* 2     
    0.2     1

// (0011) 表示循环
上方标记为高位，转为 0.010(0011)B

JS 进制转换 API

转十进制

parseInt(string, [radix])

radix – 转换的进制数，带上以免出错

// 顺便用 API 验证之前手动转换的正确性
parseInt('7FA', 16) // 2042

parseInt('7135', 8) // 3677

parseInt('11010011', 2) // 211

十进制转其它进制

numObj.toString([radix])

Number(376..toString(2)) // 101111000B

二、JS 数值存储

小数点

数值的表示根据小数点固定与否，可以分为定点数与浮点数

定点数
- 定点整数 – 小数点固定在最右边，不占位
- 定点小数 – 小数点固定在最做边，不占位
浮点数
- 小数点不固定，可以左右浮动，几乎所有计算机语言的浮点数都采用 IEEE754 标准

IEEE754

IEEE754 是二进制浮点算术标准，而 JS 正是采用此标准的双精度存储 Number 类型，即使用 64 位存储。看看高程怎么说的：

Number 类型使用 IEEE754 格式表示整数和浮点值（在某些语言中也叫双精度值）。

IEEE754 表示数据的格式如下：

  sign   exponent      mantissa/fraction
+------+---------+---------------------------+
|  1   | 2 ~ 12  |        13 ~ 64            |
+------+---------+---------------------------+
共 1 位 | 共 11 位 |       共 52 位

符号位（sign），高位第 1 位，0/1 表示正/负
指数位（exponent），高位 2 ~ 12 位
尾数位/小数位（mantissa/fraction），剩下部分。使用科学计数法表示，最高位为 1，所以该位不显式表示，所以实际能表示 53 位。（注：0D 是特殊值）

举两个🌰：

// 可切到 二、JS 数值存储 -> 小数点 的代码区，0.1 与 0.2 的标记点参考转换过程

0.1D
= 0.00011(0011)B
= 2^-4 * 1.1(0011 repeat 12 times)0011B       // 1. 中的 1 与 . 都不占尾数位 
= 2^-4 * 1.1(0011 repeat 12 times)010B        // 进一舍零
           ↑                        ↑ 
              1 + 4*12 + 3 = 52 位
              
0.2D 
= 0.(0011)B
= 2^-3 * 1.1(0011 repeat 12 times)0011B       // 1. 中的 1 与 . 都不占尾数位 
= 2^-3 * 1.1(0011 repeat 12 times)010B        // 进一舍零
           ↑                        ↑ 
              1 + 4*12 + 3 = 52 位

0.1 + 0.2 !== 0.3 *

取上方结果

0.1D + 0.2D
= 2^-3 * 0.11(0011 repeat 12 times)01B  // 指数位校准
+ 2^-3 * 1.1(0011 repeat 12 times)010B
= 2^-3 * 0.1100110011001100110011001100110011001100110011001101B
+ 2^-3 * 1.1001100110011001100110011001100110011001100110011010B
= 2^-3 * 10.0110011001100110011001100110011001100110011001100111B  // 再转换成符合 IEEE754 标准
= 2^-2 * 1.0011001100110011001100110011001100110011001100110100B
0.3D = 0.010011001100110011001100110011001100110011001100110011B   // 0.3D 二进制可参考之前的代码区，或自行使用短除法获取
                                                            ↑↑↑ 
                                                            不等

三、二进制加减运算

加法

加法不过多解释，即位数相加，逢 2 进 1。

减法

减法是重点，最终二进制的减法是使用了补码，下面从 2 – 1 这个简单的表达式来逐步演进。

原码

原码使用最高位 0/1 表示数值正/负。

尝试使用加法来表示

    2 - 1 = 1
=>  0 010 + 1 001 = 1 011 
=>  -3 !== 1

明显使用源码加法表示减法不行，因为符号位影响了数值正负却没有参与运算，接着往下看

反码与补码 *

反码存在的目的是用于快速求取补码。如下分析：

负数原码转换为补码的公式是：2^(n+1) + value，其中 n 为最高位，value 为原码。
而如果我们根据这个公式来求补码未免麻烦，于是引进了反码，反码的公式是 2^(n+1) – 1 + value。而通过归纳总结：负数原码的反码就是按位取反，再根据公式显然补码 = 反码 + 1，于是得出快速求取负数补码的方法。补码中正数不变，负数除了符号位其它位取反再加 1。

    2 - 1 = 1
=>  0 0010 + 1 0001
    0 0010 + 1 1110  // 正数补码是本身，负数除符号位取反
    0 0010 + 1 1111  // 再加 1 求取负数补码
  = 0 00001 = 1*2^0 = 1

不管用多少位表示，符号位都放到最高位。

四、JS 位运算

ECMAScript 中的所有数值都以 IEEE 754 64 位格式存储，但位操作并不直接应用到 64 位表示，而是先把值转换为 32 位整数，再进行位操作，之后再把结果转换为 64 位。

AND

与运算符/操作符 – &，对位取与，真值表与举例如下：

// 按位与
// 0 1
// +-----+-----+
// 0 | 0 | 0 |
// +-----+-----+
// 1 | 0 | 1 |
// +-----+-----+ 

2 & 10
=   00010B 
  & 01010B
------------
    00010B
=   2D

OR

或运算符/操作符 – |，对位取或，真值表与举例如下：

// 按位或
// 0 1
// +-----+-----+
// 0 | 0 | 1 |
// +-----+-----+
// 1 | 1 | 1 |
// +-----+-----+ 

2 | 10
=   00010B 
  & 01010B
------------
    01010B
=   10D

NOT *

非运算符/操作符 – ~。

正数：按位取反，求补码

负数：求补码，按位取反

举例如下：

// 按位非
// 0 1
// +-----+-----+
// | 1 | 0 |
// +-----+-----+

~ 10
= ~ 00000000000000000000000000001010B 
=   11111111111111111111111111110101B  // 取反
=   10000000000000000000000000001011B  // 求补码
=   -11

~ -10
= ~ 10000000000000000000000000001010B 
=   11111111111111111111111111110110B  // 求补码
=   00000000000000000000000000001001B  // 取反
=   9

按位非快速求值的技巧是：对数值取反并减 1

XOR

异或运算符/操作符 – ^，对位取异或（可理解为异，位上的值相异为真，否则为假），真值表与举例如下：

// 按位异或
// 0 1
// +-----+-----+
// 0 | 0 | 1 |
// +-----+-----+
// 1 | 1 | 0 |
// +-----+-----+ 

2 ^ 10
=   00010B 
  ^ 01010B
------------
    01000B
=   8D

Left shift

左移运算符/操作符 – <<，符号位不变，所有位向左移动多少位，空位补零，举例如下：

49 << 6
=    00000000000000000000000000110001B 
                               ↑↑↑↑↑↑
  << 00000000000000000000110001000000B
                         ↑↑↑↑↑↑
=    3136D

-11 << 2
=    10000000000000000000000000001011B 
                                 ↑↑↑↑
  << 10000000000000000000000000101100B
                               ↑↑↑↑
=    -44

Right shift *

右移运算符/操作符 – >>，符号位不变，所有位向右移动多少位，空位补符号位值，举例如下：

49 >> 6
=    00000000000000000000000000110001B 
                               ↑↑↑↑↑↑
  >> 00000000000000000000000000000000B
                                     ↑↑↑↑↑↑           
=    0D

-11 >> 2
=    10000000000000000000000000001011B 
=    11111111111111111111111111110101B   // 求补码
                                 ↑↑↑↑
  >> 11111111111111111111111111111101B   // 补码转原码 -> 取反再 +1
                                   ↑↑↑↑
=    10000000000000000000000000000011B
=    -3

Unsigned right shift

无符号右移运算符/操作符 – >>>，所有位向右移动多少位，空位补零，举例如下：

// 正数 >>> 与 >> 一样，就不举例子了

-11 >>> 2
=    10000000000000000000000000001011B 
=    11111111111111111111111111110101B   // 求补码 
   ->
 >>> 00111111111111111111111111111101B                                      
     ->
=    10000000000000000000000000000011B
=    1073741821

五、大数相加

有限存储一定会碰到大数计算的问题，让我们通过一个实例来学习下处理大数相加的技巧：

// 思路：把数字类型转成存储每一位的数组，使用竖式计算：反转数组，对位相加，满十进一
// 注意点：
// 1.更新进位
// 2.检查最高位为零则截断

function string2array(s){
  return String(s).split('').reverse().map(val => parseInt(val))
}

function bigAdd(s1, s2){
  const list1 = string2array(s1)
  const list2 = string2array(s2) 
  let length
  const sum = Array.from(Array(length = Math.max(list1.length + 1, list2.length + 1)), _ => 0)
  let up = 0
  for (let i = 0; i < length + 1; i++) {
    list1[i] ?? (list1[i] = 0)
    list2[i] ?? (list2[i] = 0)
    sum[i] = list1[i]  + list2[i] + up
    up = sum[i] > 9 ? 1 : 0
    sum[i] = sum[i] % 10
  }
  sum[sum.length - 1] === 0 && sum.pop()
  return sum.reverse().join('')
}

// test case
bigAdd('1234567890343', '123434256567890')

更多大数问题可参考这篇文章进一步学习。

六、总结

补码是为了解决减法，有负数的地方都离不开补码的应用
关于位运算的使用，我的看法是业务代码还是少用，毕竟要考虑可读性
位运算部分根据高程使用 32 位示例，而且之前有文提及由于这个原因位运算性能会差些（其实相差不大），ES5 规范中也确实先转 32 位，但在最新的 ES2021 规范中确不是如此。关于新版高程（第四版）要给大家提个醒：有些内容是参考 ES3 的，比如 execution context 中仍然使用 variable object 来解释，之后有机会再写一篇关于函数执行的文章。

写到这里二进制表达方式、存储、运算相信大家已经有所了解，要熟练使用还有赖于亲自动手编码，而且本文也只能带大家对二进制有个初步了解，如果想更深入课参考以下链接学习。