前端

JS位运算符的妙用与原理

2019-11-27  本文已影响0人  科研者

很多高级语言的开发者都容易忽略位运算符的使用技巧，因为他们总感觉位运算符是底层开发的专利；其实，这是错误的，通过巧妙地使用位运算符，常常可以获取性能上的提升和代码的精简；为了在 JavaScript 中充分利用位运算符，我挖掘了一些实用的技巧；本文就集中讲解下位运算符在 JavaScript 中的巧妙使用方法及其原理；

提示：如果想忽略基础知识，直接看技巧，可从 五、取整 开始看起

目录

内容

一、概念

在讲解位算符的技巧和原理之前，需要选了解一下一些概念：

二、位运算符的特性

在 JavaScript 中，位运算符具备以下特性：

三、位运算符介绍

运算符 用法 描述
按位与（AND） a & b 对于每一个比特位，只有两个操作数相应的比特位都是1时，结果才为1，否则为0。
按位或（OR） a | b 对于每一个比特位，当两个操作数相应的比特位至少有一个1时，结果为1，否则为0。
按位异或（XOR） a ^ b 对于每一个比特位，当两个操作数相应的比特位有且只有一个1时，结果为1，否则为0。
按位非（NOT） ~ a 反转操作数的比特位，即0变成1，1变成0。
左移（Left shift） a << b 将 a 的二进制形式向左移 b (< 32) 比特位，右边用0填充。
有符号右移 a >> b 将 a 的二进制表示向右移 b (< 32) 位，丢弃被移出的位。
无符号右移 a >>> b 将 a 的二进制表示向右移 b (< 32) 位，丢弃被移出的位，并使用 0 在左侧填充。

四、特殊的值

下面罗列了一些常用的特殊的值的 及 其对应的机器数 和 其获取方式；

五、取整

去掉浮点数的小数部分称为取整；

我们常用的取整方式如下：

这些函数都是通过对操作数应用一定算法来实现的；下面提供的这些用位运算符取整的方法，要比这些高效得多，且简洁；

原理：
上面说了，所有的位运算符都会把操作数转为 32 位整数；所以，当位运算符作用于浮点数时，就会将和浮点数转为32位整数； 这是基本原理，但并不是所有的位运算符都适合用于取整操作，因为有些运算符的操作过程是不可逆的，或者会改变操作数的整数部分的值；下面是我 设计 并 挑选 的几个可用于取整的操作；

方式1：与0进行或运算 x|0

将一个数 x 通过与 0 进行或运算 x ^ 0，可直接得到 x 的整数部分；
示例：

4.3 | 0  // 4
-4.6 | 0  // -4

原理：
根据上表中 或 定义，可得：1 | 0 == 1 和 0 | 0 == 0；
即：任何位 x 与 0 或 的值都与原来位 x 相等；

而数值 0 对应的机器数是 32 个 0 ，所以，与 0 或的位操作运算导致了 操作数 去掉了小数部分，而且不会改变操作数的整数部分的值；从而实现了取整的效果；

方式2：与-1进行与运算x&-1

将一个数 x 通过与 -1 进行与运算 x & -1，可直接得到 x 的整数部分；
示例：

4.3 & -1  // 4
-4.6 & -1  // -4

原理：
根据上表中 与 定义，可得：1 & 1 == 1 和 0 & 1 == 0；
即：任何位 x 和 1 做 与运算 的值都与原来位 x 相等；

而数值 -1 对应的机器数是 32 个 1 ，所以，与 -1 与的位操作运算导致了 操作数 去掉了小数部分，而且不会改变操作数的整数部分的值；从而实现了取整的效果；

方式3：与0异或 x^0

将一个数 x 通过与 0 异或 x ^ 0，可直接得到 x 的整数部分；
示例：

4.3 ^ 0  // 4
-4.6 ^ 0  // -4

原理：
根据上表中 异或 定义，可得：1 ^ 0 == 1 和 0 ^ 0 == 0；
即：任何位 x 与 0 异或 的值都与原来位 x 相等；

而数值 0 对应的机器数是 32 个 0 ，所以，与 0 异或的位操作运算导致了 操作数 去掉了小数部分，而且不会改变操作数的整数部分的值；从而实现了取整的效果；

方式4：双非运算 ~~x

对一个数 x 进行两次非运算，可直接得到该数 x 的整数部分；
示例：

~~4.3  // 4
~~(-4.6) // -4

原理：
非的位操作符使操作数去掉了小数部分，而双非操作会使操作数的整数部分反转之后再反转从而变回了原来的整数值；

方式5：与同一个数两次异或 x^a^a

对一个数 x 进行两次非运算，可直接得到该数 x 的整数部分；
示例：

4.3^5^5  // 4
-4.6^-3^-3 // -4

原理：
根据上表中 异或 定义，可得：

1 ^ 0 == 1
0 ^ 0 == 0

1 ^ 1 == 0
0 ^ 1 == 1

即：

所以：

所以：

所以：异或的位操作符使操作数去掉了小数部分，而与同一个数双异或的操作会使操作数的整数部分的值不变；

方式6：左移0位 x<<0

将一个数 x 左移0位，可直接得到该数 x 的整数部分；
示例：

4.3<<0 // 4
-4.6<<0 // -4

原理：
左移的位操作符使操作数去掉了小数部分，而左移0位相当于没有移位，也使得保留了操作数的整数部分；

方式7：有符号右移0位 x>>0

对一个数 x 进行有符号右移0位，可直接得到该数 x 的整数部分；
示例：

4.3>>0 // 4
-4.6>>0 // -4

原理：
有符号右移的位操作符使操作数去掉了小数部分，而有符号右移0位相当于即没有移位也没有改变操作数的符号位，也使得保留了操作数的整数部分；

方式8：对正数无符号右移0位 x>>>0

对一个正数 x 进行无符号右移0位，可直接得到该数 x 的整数部分；
示例：

4.3>>>0 // 4

原理：
无符号右移的位操作符使操作数去掉了小数部分，而无符号右移0位相当于没有移位，即：不会改变操作数的机器数；但是会使操作数变成正数（即：计算机会把该机器数作为一个正数来看代）；不过，当操作数本身就是正数时，无符号右移动 0 位就相当于不会改变操作数的正负性，所以也就实现了 保留正数操作数的整数部分；

方式9：无符号右移0位再与0进行或运算 x>>>0|0

对一个数 x 进行无符号右移0位后，再与0进行或运算，可得到该数 x 的整数部分；
示例：

4.3>>>0|0  // 4
-4.6>>>0|0 // -4

原理：
与 x>>>0^0 的原理相同：无符号右移的位操作符使操作数去掉了小数部分，而无符号右移0位相当于没有移位，即：不会改变操作数的机器数；但是会使操作数变成正数（即：计算机会把该机器数作为一个正数来看代）；为了让计算机把该机器数当作一个有符号32位整数，需要对该机器数应用一次无变化位运算，比如：与0相或；这样，便可把机器数所表示的值恢复成原来的值；所以，所以也就实现了 保留操作数的整数部分；

方式10：无符号右移0位再与0进行异或运算 x>>>0^0

对一个数 x 进行无符号右移0位后，再与0进行异或运算，可得到该数 x 的整数部分；
示例：

4.3>>>0^0  // 4
-4.6>>>0^0 // -4

原理：
与 x>>>0^0 的原理相同：无符号右移的位操作符使操作数去掉了小数部分，而无符号右移0位相当于没有移位，即：不会改变操作数的机器数；但是会使操作数变成正数（即：计算机会把该机器数作为一个正数来看代）；为了让计算机把该机器数当作一个有符号32位整数，需要对该机器数应用一次无变化位运算，比如：与0异或；这样，便可把机器数所表示的值恢复成原来的值；所以，所以也就实现了 保留操作数的整数部分；

六、与2的幂相乘

求一个数 x 与 2 的 n 次方的幂 乘积 除了 用算术运算符 x * (2 ** n) 的方式外，也可用位运算符 向 左移 n 位 的方式：

x << n

示例

5 << 3  // 求 5 * 2 的 3 次方的 幂

原理
对于 二进制的 移位操作，每向左移一位，就相当于乘了 基数，即 2 ，左移 n 位，就相当于 乘了 n 次 基数，即 基数的 n 次方，也即 2 的 n 次方，所以， 一个数 左移 n 位，就相当于 乘了 2的 n次方；

七、位开关

定义(个人定义，非官方)：位开关 就是 用二进制数中一位来表示一个二态量；

假如，我们需要表示4个灯泡 A、B、C、D 的状态；

通常，比较直观的设计方案是下面这样：

但是，这样设计的问题是：当我们需要传递 这些灯泡的状态时，我们需要传递 4 个参数，比较麻烦；

我们改用下面这个设计方案：

这样，我们只需要用一个参数 就可以传递这些灯泡的状态；

获取某个灯的状态：
如果我们想知道某个灯泡（比如 灯B）的状态，我们可以根据之前定义的位序列 DCBA 来写出 灯B 的位掩码 mask = 0b0010 ，然后将 表示灯状态的数 bulb 与 位掩码 mask 做 位与运算 bulb & mask得到，如果值不为 0 ，则表示 灯B 的状态是 开的；

判断在某几灯中，是否至少有一个是开着的：
如果我们想知道某几个灯泡（比如 灯C、灯B）是否至少一个是开着的，我们可以根据之前定义的位序列 DCBA 来写出 灯C、灯B 的位掩码 mask = 0b0110 ，然后将 表示灯状态的数 bulb 与 位掩码 mask 做 位与运算 bulb & mask得到，如果 值不为 0 ，则表示 灯C 和 灯B 至少一个是开着的；

判断某些灯是否是都开着的：
如果我们想知道某几个灯泡（比如 灯C、灯B）是否是都开着的，我们可以根据之前定义的位序列 DCBA 来写出 灯C、灯B 的位掩码 mask = 0b0110 ，然后将 表示灯状态的数 bulb 与 位掩码 mask 做 位与运算，再将运算的结果 与 位掩码 mask 做相等比较 (bulb & mask) == mask，如果值不为 true ，则表示 灯C 和 灯B 都是开着的；

总结

用一个二进制位来表示一个 二态量，则多个二态量便可以用一个二进制位序列来表示；这个二进制位序列可以作为一个数存储在一个变量中；我将表示这样二进制序列的数叫做 开关序列；

通过与 开关序列 做 与 运算 来获取部分二态量信息的二进制序列 叫做 这些二态量的 掩码；掩码 的表示方法是：将不需要的二态量的二进制位置为 0 ，将需要的二态量置为 1 ，这样得到的一个二进制位序列 就是 这些所需量 的 掩码；

获取某个二态量的值

将 开关序列 与 该二态量的 掩码 做 位与 运算，运算的结果便是该二态量的值；

switchSeq & mask

示例：

var switchSeq = 0b0110;   //包含多个二态量入信息的开关序列
var mask = 0b0010;      //第二个二态量的掩码
var second = switchSeq & mask;      //将 开关序列 与 该二态量的 掩码 做 位与 运算 来 获取第二个二态量的值

原理：
根据上表中 与 定义，可得：1 & 1 == 1 和 0 & 1 == 0；
即：任何位 x 和 1 做 与运算 的值都与原来位 x 相等；任何位 x 和 0 做 与运算 的值是 0；

而 掩码中 不需要的二态量的二进制位被置为了 0 ，在与 开关序列 相与 时，不需要的位就被 置为了 0 ；掩码中 需要的二态量置为 1 ，在与 开关序列 相与 时，需要的位的值 就被保留了下来 ；所以，开关序列 与 某个二态量的 掩码 做 与运算 后，得到的值就是 该二态量的值；

判断是否至少包含某些二态量中的一个

将 开关序列 与 这些二态量的 掩码 做 位与 运算 ，如果结果不为 0 ，则表示 开关序列 中 包含这些二态量中的至少一个；如果结果 为 0 ，则表示 开关序列中 不包含 这些二态量中的任何一个；

switchSeq & mask

示例：

var switchSeq = 0b0110;   //包含多个二态量入信息的开关序列
var mask = 0b0011;      //第一、二个二态量的掩码
var firstOrSecond = switchSeq & mask;      //将 开关序列 与 第一、二个二态量的 掩码 做 位与 运算 ，如果结果不为 0 ，则表示 开关序列 中 包含第一、二个二态量中的至少一个

原理：
根据上表中 与 定义，可得：1 & 1 == 1 和 0 & 1 == 0；
即：任何位 x 和 1 做 与运算 的值都与原来位 x 相等；任何位 x 和 0 做 与运算 的值是 0；

而 掩码中 不需要的二态量的二进制位被置为了 0 ，在与 开关序列 相与 时，不需要的位就被 置为了 0 ；掩码中 需要的二态量置为 1 ，在与 开关序列 相与 时，需要的位的值 就被保留了下来 ；所以，开关序列 与 某个二态量的 掩码 做 与运算 后，得到的值就是 该二态量的值；

判断是否包含某些二态量中的每一个

将 开关序列 与 这些二态量的 掩码 做 位与 运算 ，再让 运算结果 与 掩码 相 相等比较，如果相等，则表示 开关序列 包含这些二态量中的每一个；如果不相等 ，则表示 开关序列中 并不包含 这些所有的二态量；

(switchSeq & mask) === mask

示例：

var switchSeq = 0b0110;   //包含多个二态量入信息的开关序列
var mask = 0b0011;      //第一、二个二态量的掩码
var all = (switchSeq & mask) === mask;      //将 开关序列 与 第一、二个二态量的 掩码 做 位与 运算 然后再 与 掩码 做相等比较，如果相等，则表示 开关序列 包含这些二态量中的每一个；如果不相等 ，则表示 开关序列中 并不包含 这些所有的二态量；

原理：
根据上表中 与 定义，可得：1 & 1 == 1 和 0 & 1 == 0；
即：任何位 x 和 1 做 与运算 的值都与原来位 x 相等；任何位 x 和 0 做 与运算 的值是 0；

而 掩码中 不需要的二态量的二进制位被置为了 0 ，在与 开关序列 相与 时，不需要的位就被 置为了 0 ，这与 掩码 中的值一样；掩码中 需要的二态量置为 1 ，在与 开关序列 相与 时，需要的位的值 就被保留了下来 ；所以，如果 开关序列 包含所有这些需要的位，则 掩码 在与 开关序列 相与 时，需要的位的值 就是 1 ，即：与 掩码 中的值一样；所以，如果 开关序列 包含某些二态量中的每一个，则 开关序列 与 这些二态量的 掩码 做 位与 运算后的值 会和 掩码 相等；

八、求对2的幂的余数

JavaScript 语言自带取余运算符 % ，但如果是求 对 2的整数次幂 的余数，则还有另一个更加高效的方法；

求 数x 对 2 的 n 次幂 的余数，可用 数 x 与 从右往左连续 n 个位是 1 的二进制数 mask 做位与运算 x & mask，运算的结果就是 所求余数；

示例：
求 10 对 2的3次方(也就是8)的余数；

var x = 10; 
var mask = 0b111;      //因为要求 对 2的3次方的幂的余数，所以 mask 为3个二进制1；
var mod = x & mask;      // mod 即为 10 对 2的3次方的幂的 余数

原理：
将 数 x 与 从右往左连续 n 个位是 1 的二进制数 mask 做 位与 运算 x & mask 后，数 x 的 最右边的 n 位的值就被保留了下来，其它位都置为了 0 ，此时的数值正是小于 2的次方的幂的数，也就是 对 2的n次方的余数；

九、奇偶判断

判断一个整数 x 是奇数还是偶数的方法是：求这个数对2的余数 x % 2，如果是余 零 ，则该数为偶数，如果余数不是零，则该是奇数；

由于 2 是 2 的 1 次方的幂，所以，可以用 求对2的幂的余数 中所述的方法，让该数 与 1 相 相与 x & 1，如果结果是 零，则该数是偶数，如果该数不为 零 ，则该数是奇数；

所以，判断一个数 x 是奇数还是偶数的方法有 2 种：

十、交互两个数

交互两个整数变量 a、b 的方法有以下几种：

方法1:中间变量

var temp = a; // 定义临时变量，用来临时保存 a 的原始值；
a = b;   // 次 b 赋值给 a；
b = temp;  // 将 a 的原始值 赋值给 b；

方法2:表达式暂存

a = [b, b = a][0];

或

a = {a:b, _:b = a}.a;

这种方式是利用 表达式 的计算 顺序 将 原始值 暂存 在 数组的元素 或 对象的属性 中 来 实现 临时变量 的效果；

方法3:异或运算

a ^= b;
b ^= a;
a ^= b;

数学证明：
上面给出的是代码；代码的变量是动态的，数学的变量是静态的，为了方便证明，先把方面的代码改成如下等效形式：

等效代码：

t = a ^ b;
b = t ^ b;
a = t ^ b;

然后用数学静态变量的方式来等效表示上面的等式，即：用 a、b 表示代码中初始的 a、b 值；用 x 表示 代码中最终 a 的值，用 y 表示代码中最终的 b 的值；
等效的数学表达式：

t = a ^ b;
y = t ^ b;
x = t ^ y;

用数学符号表示：

t = a⊕b
y = t⊕b
x = t⊕y

证明之前，需要选证明一个公式：

(a⊕b)⊕b = a

即： a 与 b 异或的值 再与 b 异或，最终的结果 等于 a ；

(a⊕b)⊕b = a证明过程：

异或性质推导

所以，就有：

交换两个数的证明

所以：

y = a
x = b

又因为 x 表示 代码中最终 a 的值，y 表示代码中最终的 b 的值；

所以，对于代码

t = a ^ b;
b = t ^ b;
a = t ^ b;

执行完成后，最终 b 的值 是 原来 a 的值，最终 a 的值，是原来 b 的值，从而实现了 变量 a 和 b 的值互换的操作；

上一篇下一篇

猜你喜欢

热点阅读