JavaScript 位运算学习
这几天粗略的阅读了一下 AngularJS 的源码,在这个过程中发现有这么两段代码挺有意思的:
1 | var manualLowercase = function (s) { |
这两段代码用来处理字母大小写转换,由于某些国家(土耳其)使用
toLowerCase()
和toUpperCase()
不能正确的转换字母大小写,因而需要手动的处理。
为什么说这两段代码有意思?其实是觉得其中用位运算处理字母大小写的代码很巧妙,其核心代码如下:
1 | ch.charCodeAt(0) | 32 // 大写转小写 |
在分析两段代码之前,先来回顾一下 JavaScript 中的两个概念:整数和位运算。
从严格意义上讲,ECMAScript 中有两种类型的整数:有符号的整数(正数和负数)和无符号的整数(只有正数)。而默认情况下 JavaScript 中的整数都是有符号的。
而在不考虑 ECMAScript 中数字格式存储与转换(为 32 位)的情况下,实际上我们操作的都是 32 位的整数。而对于上面提到的有符号整数而言,其中前 31 位(end<-start
)表示数字的值,最后1位表示符号位(0
表示正,1
表示负)。
这里提到的 32 位的整数在计算机底层都是使用二进制格式存储的,而这个二进制由 0
和 1
组成,其中每一位都有对应的十进制数字结果,整个二进制数值代表的十进制结果由所有这些位对应的十进制数字之和。
这篇文章中不考虑负数的情况,一个 32 位二进制格式的数字看起来如下所示,这里以 10 为例:
1 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 |
二进制数字计算的方式:
number ( Math.pow(2, index))
,这里的number
表示二进制中对应位上的数值 0/1,index
表示该数值在整个二进制格式的数字中的索引。注意一个二进制格式的起始点在右侧。那么上面的数字就等于:
1 * Math.pow(2,3) + 1 * Math.pow(2, 1) = 10
。
前面提到了,这些二进制的数字实际上都是在计算机的底层完成的,而 ECMAScript 中刚好提供了二进制运算相关的操作符,这些操作符都是直接对运算数进行二进制操作的,并且都是发生在幕后的。
JavaScript 中有 7 个位运算相关的运算符:
- 按位非(NOT) - 用一个波浪线”
~
“表示,对二进制的每一位进行取反操作,即将0
变成1
,将1
变成0
。 - 按位与(AND) - 用一个和好”
&
“表示,必须有两个操作数,先对齐二进制位,然后把对应位都为1
的为筛下来,其他的都为0
。 - 按位或(OR) - 用一个竖线”
|
“表示,也必须有两个操作数,对齐位之后只要对应位有 1 就筛下来,只有同时位 0 时才返回0
。 - 按位异或(XOR) - 用一个插入符号”
^
“表示,也必须有两个操作数,对齐位之后不同的返回 1,相同的返回 0。 - 左移 - 用两个小于号”
<<
表示,顾名思议,将操作数左移指定位数,右侧空位用 0 补齐。 - 有符号右移 - 用两个大于号”
>>
“表示,保留符号位,剩下的右移指定位。 - 无符号右移 - 用三个大于号”
>>>
“表示,往右侧移动指定位数。
以上这些位运算符,最终操作的都是二进制数值。
在上面的代码中分别涉及到了按位非,按位与,按位或三种运算。先来针对上面的两段代码讲解一下这三个位运算符:
1 | ch.charCodeAt(0) | 32 |
这段代码通过正则表达式匹配到给定字符串中的每个大写字母: A-Z
;接下来使用字符串对象的 charCodeAt()
方法拿到该字符对应的 Unicode 编码,恰好这个编码是一个数字;最后使用按位或运算获取到另外一个数字。
为什么这里执行对数值 32 的按位或运算呢?当然这肯定不是空穴来风。那么我们先从大写字母及对应的 Unicode 值分析看看。不难发现,A-Z
对应的 Unicode 编码分别为 65-90
;而这写编码对应的二进制表示分别为:1000001
… 1011010
。再看看小些字母对应的数据:其 Unicode 编码分别为:97-122
,对应的二进制表示分别为:1100001
…1111010
。最后将它们放入一张表格中对比如下:
提示:使用
(1).toString(2)
便可以拿到每个数字对应的二进表示法的有效位。
大写字母二进制有效位 | 1000001 |
… | 1011010 |
---|---|---|---|
小写字母二进制有效位 | 1100001 |
… | 1111010 |
在这个表格中没有完整列出每个字母对应的二进制有效位。但是通过完整的对比不难发现,大写字母与小写字母的二进制有效位都是 7 位,对这些数值进行对不不难发现大小写字母的二进制有效位中:大写字母的第 6 位为 0;而小写字母的第 6 位为 1;而每个大小写自己的二进制有效位中刚好只有这一位不同。
因此我们在求值大写字母的对应的小写字母的二进制数值时转换大写字母的二进制数值第 6 位即可,其他的位是一样的不用转换。而第 6 位为 1 时,其对应的十进制数值刚好是 32(1 * Math.pow(2, 5)
),32 对应的二进制数值的有效位为:100000
。
那么如何转换这里的第 6 位呢?我们的目的是将大写字母二进制数值第 6 位的 0 转换为 1,而其他的位不变。最终我们只需要拿一个刚好第 6 位为 1,其他位为 0 的二进制数值与大写字母的二进制数值进行位运算操作即可,这个能够用来进行有效位运算的二进制数值则为 100000
,而 JavaScript 中的按位或操作刚好能有做到这一点。
而在 JavaScript 中,我们并不能直接操作一个二进制的数值,二进制的运算都是在低层完成的,在 JavaScript 中这些都是按位运算符的使命。那么,在前面使用 charCodeAt()
方法已经拿到了大写字母对应的 Unicode 编码-即一个有效的十进制数字;而 100000
对应的十进制数字为 32。
由此得出结论,使用大写字母对应的 Unicode 编码与 32 作按位或运算便能正确的拿到其对应的小写字母的 Unicode 编码,其操作过程如下:
以大写字母 A
为例:
1 | 0 | 0 | 0 | 0 | 0 | 1 |
---|---|---|---|---|---|---|
1 | 0 | 0 | 0 | 0 | 0 | |
1 | 1 | 0 | 0 | 0 | 0 | 1 |
如此,便拿到了一个二进制数值:1100001
,对应的十进制数字为 97(parseInt(‘1100001’, 2))。最后使用 String 对象的 fromCharCode()
方法得到的字符便是大写字母 A
对应的小写字母 a
。
整个转换的过程中,所有的这些操作实际上都是在底层(?内存中)完成的。
上面剖析了大写字母转小写字母的过程。接下来再看看小写字母转大写字母。在上面的代码中,我们可以看到转大写字母的代码为:
1 | ch.charCodeAt(0) & ~32 |
首先,同大写字母一样,使用字符串对象 (String) 的 charCodeAt()
方法拿到对应的 Unicode 编码(也是一个十进制数值)。在上面的字母二进制数值对比表格中我们已经找到了规律:即转换每个字母对应的二进制数值的第 6 位即可。那么如何将小写字母的二进制数值的第 6 位 1 转换为 0,而其位不变呢?
前面将大写字母的第 6 位 0 转为 1,我们使用了按位或来保证将第 6 位正确的转换为 1。而这一次小写转大写的过程中,我们必须保证正确的将第 6 位 1 转换为 0,其他位不变即可。由此得出,这一次进行位运算的基本条件必须保证第二个操作数的第 6 位为 0,而其他位该是 1 的是 1,该是 0 的是 0。
那么如何做到这一点呢?根据位运算的特点以及上面的分析,我们保证第 6 位不同即可,那么拿 011111
与小写字母的二进制数值进行按位与运算运算即可。而对 32 进行按位非运算的结果刚好为 011111
。
以小写字母 a
为例
1 | 1 | 0 | 0 | 0 | 0 | 1 |
---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | |
1 | 0 | 0 | 0 | 0 | 0 | 1 |
这里不一定必须是
011111
。比如拿一个完整的 32 位11111111111111111111111111011111
也可以。但是在上述环境中,011111
就能满足需求,而这个二进制数值对应的数值刚好是对 32 进行按位非的运算结果。
根据前面的分析,这样就拿到了大写字母 A 对应的二进制数值,再对它编码便可以返回最终的大写字母。
至此,对 AngularJS 中这两段代码的分析就完成了。也算是对 JavaScript 中的位运算做了一次巩固,温习。
其实 JavaScript 中的位运算远远不止这一点,我们还可以使用其他位运算符做到很多事情。下面是一些例子,不妨分析一下其运算原理:
1 | // 获取 0-max 之间随机整数 |
一些本文中用到的代码片段:
1 | // 获取字符 Unicode 编码值 |
写在最后,虽然代码很小,但是其中学问还是蛮大的,仔细分析一下感觉收获很多。在这里尤其感谢我的导师 @toobug 不厌其烦的在 KFC 给我讲解了很多基础知识。
参考资料: