初探js按位操作

[tiodot]

概述

虽然在js的世界中，使用的数字类型都是十进制的，然而经常可见一些按位操作：

if (~xxx.indexOf(y)) {}  // ==> xxx.indexOf(y) !== -1

n >> 1 // ==> n / 2 

自己写码虽很少用按位操作符，但看到这些代码时，如果没有一些注释理解起来却是有些难度。

按位操作符（Bitwise operators） 将其操作数（operands）当作32位的比特序列（即二进制表示）进行操作，但其返回值依然是标准的JavaScript数值。

在js中可以使用toString将一个数值装换成二进制形式，当然也可以使用parseInt将一个二进制字符串解析成数值：

let b = (9).toString(2); // => 1001

parseInt(b, 2)  // => 9

按位操作符类型

运算符	用法	描述
按位与(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 在左侧填充。

1. 按位与(&)

对每对比特位执行与（&）操作。只有 a 和 b 都是 1 时，a & b 才是 1:

a	b	a & b
0	0	0
0	1	0
1	0	0
1	1	1

利用这个特性，可以判断一个数是否是2的指数倍:

function isPowerOfTwo (x) {
    return x && !(x & (x - 1));
}

其原理是，假设一个数n=2^m，用二进制（31位表示）表示n时，其第31-m位总是为1，其余都是0，而n-1的二进制表示时，其31-m-1至31都是1，其余都是0，例如对于64：

// 64的二进制
0000000000000000000000001000000
//而63的二进制
0000000000000000000000000111111

同理也可以利用按位与(&)的特性来判断一个数是否是偶数/奇数：

// 偶数的二进制最后一位总是为0， 如果一个数n是偶数，则n&1 => 0
function isEven(n) {
  return !(n&1);  // !的优先级比&高，故需要使用括号
}

2. 按位或(|)

对每一对比特位执行或（|）操作。如果 a 或 b 为 1，则 a | b 结果为 1:

a	b	a | b
0	0	0
0	1	1
1	0	1
1	1	1

因为位运算只对整数有效，遇到小数时，会将小数部分舍去，结合或运算的特性，可以很容易实现类似Math.floor向下取整的功能:

function floor(n) {
  return n | 0; // 自动舍弃小数部分
}

3. 按位异或(^)

对每一对比特位执行异或（^）操作。当 a 和 b 不相同时，a ^ b 的结果为 1：

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

当一个数n, n ^ n结果总是为0，而任意一个数与0进行异或操作，其结果都不会变。所以利用异或操作，可以很容易类似「缺失的数字」，一个只包含数字的数组中，数字本应都是成对出现，由于意外某个数字丢失，需要找个这个丢失的数字，例如[1, 2, 3, 1, 3]的缺失数字为2：

function findLostNum(n) {
  let result = 0;
  n.forEach(num => {result ^= num});
  return result;
}

使用异或这个特性也可以交换两个变量的值：

let a = 1, b = 2;
a ^= b; //假设两个变量a'和b'用于保存新的a和b的值 =>  a' =  a ^ b
b ^= a; //此处a其实是a'  => b' = b ^ a' === b ^ (a ^ b) === (b ^ b) ^ a === a
a ^= b; // 此时b其实已经为b' => a' = a' ^ b' === a ^ b ^ a = b
console.log(a, b) // 等价于输出 a' 和 b'  => 2, 1

平时求两个数值的和，可以简单的使用a + b，然而某一天编译器对+解析出现了异常（虽然不现实，假设一下...），不允许用+求数值和之后该怎么办？
答案就是结合异或操作(^)好按位与(&)操作：

function getSum(a, b) {
  let sum = a;
  while(b != 0) {
      sum = a ^ b; // 异或操作，移除相同二进制位
      b = (a & b) * 2; // 与操作，获取相同二进制， 然后左移1位，等价于十进制加法操作中的相加超过10时，需要往前进的数。
      a = sum; 
  }
  return sum;
}

然后实例论证一下上述过程，假如这两个数a、b分别为7、3，其对应的二进制形式分别为0111和0011，正常二进制数加法思路和十进制数加法都一样为：

1. 最末位数进行相加，即1+1 结果为2 ，需要往前一位进1，然后把结果置为0；
2. 倒数第二位进行相加，此时需要考虑进位数了，即1 + 1 + 1(进位)结果为3， 往前近一位，结果至为1；
3. 然后依次进行倒数第三位，倒数第四位的计算... 最终结果为1010

进行按位操作时异或操作在不考虑进位数前提下，只关注相加之后各位的结果值(1+1 => 0, 1 + 0 => 1)，通过与操作统一处理进位数 ((1 & 1) * 2 => 1 * 2 => 10(二进制，相当于进了一位))

初始值	异或运算	与运算	每轮循环结果
a=0111, b=0011	0100	0011	a=0100, b = 0110
a=0100, b = 0110	0010	0100	a=0010, b = 1000
a=0010, b = 1000	1010	0000	a = 1010, b = 0

4. 按位非(~)

对每一个比特位执行非（~）操作。~a 结果为 a 的反转，对任一数值 x 进行按位非操作的结果为 -(x + 1)。例如，~5 结果为 -6。

9 (base 10) = 00000000000000000000000000001001 (base 2)
               --------------------------------
~9 (base 10) = 11111111111111111111111111110110 (base 2) = -10 (base 10) // 为什么是-10？

由于计算机都是以补码, 具体可参考原码, 反码, 补码 详解形式存储数字的，故：

11111111111111111111111111110110 (base 2)   // 补码形式
-> 按位取反 + 1, 符号位不变
1000000000000000000001001(base 2) + 1 = 1000000000000000000001010(base 2) = -10 (base 10)

利用其反转的特性，可以很容易实现类似Math.abs的功能:

function abs (n) {
    let a = n >> 31; // 通过移位获取符号位， 如果是正数 a为0，反之为-1
    return a === 0 ? n : (~n + 1);
}

还用常见的:

~xxx.indexOf(x) // 利用的就是 ~(-1) === 0 如果不存在则返回空

5. 左移(<<)&右移(>>)

按位移动操作符有两个操作数：第一个是要被移动的数字，而第二个是要移动的长度。移动的方向根据操作符的不同而不同。平时用的最多的就是 n >> 1 === n / 2 并向下取整，还有 n << 1 === n*2。
可以结合按位或运算，给定一个数n，计算不超过n的2的最大倍数m，例如n=15，则m=8：

function largestPower(N) {
    //将右边所有位都置为1.
    N = N | (N>>1);
    N = N | (N>>2);
    N = N | (N>>4);
    N = N | (N>>8);
    N = N | (N>>16);
    return (N+1)>>1;
}

总结

按位操作虽说不易，但在某些计算上，使用得当的情况下可以简化代码，效率或许也会有所提升哦，尤其是在需要使用标志位时，像封装可以打印不同等级(All, Debug, Waring)等提示信息的log.js。

参考

1. MDN-按位操作符
2. Ten Ways to Check if an Integer Is a Power Of Two in C
3. Real world use cases of bitwise operators
4. 巧用 JAVASCRIPT 中的位运算
5. 位操作基础篇之位操作全面总结
6. Number Systems: An Introduction to Binary, Hexadecimal, and More
7. 我们要不要在 JS 使用二进制位运算？