tiodot / tiodot.github.io

总结归纳--做的东西不是每一件都留到现在 但是能通过实践,收获了如何构建一套系统,一套工具的方法论
https://xchb.work
8 stars 0 forks source link

初探js按位操作 #28

Open tiodot opened 7 years ago

tiodot commented 7 years ago

概述

虽然在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,其对应的二进制形式分别为01110011,正常二进制数加法思路和十进制数加法都一样为:

  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 使用二进制位运算?