【转+补充】深入研究js中的位运算及用法

转载自【博客园-不疯魔不成活】

《深入研究js中的位运算及用法》

什么是位运算？

位运算是在数字底层（即表示数字的 32 个数位）进行运算的。由于位运算是低级的运算操作，所以速度往往也是最快的（相对其它运算如加减乘除来说），并且借助位运算有时我们还能实现更简单的程序逻辑,缺点是很不直观，许多场合不能够使用。

位运算只对整数起作用，如果一个运算子不是整数，会自动转为整数后再运行。虽然在 JavaScript 内部，数值都是以64位浮点数的形式储存，但是做位运算的时候，是以32位带符号的整数进行运算的，并且返回值也是一个32位带符号的整数。

关于二进制
  • ECMAScript中的所有数值都以IEEE-754 64位格式存储，但位操作符并不直接操作64位的值，而是以32位带符号的整数进行运算的，并且返回值也是一个32位带符号的整数
  • 这种位数转换使得在对特殊的NaN和Infinity值应用位操作时，这两个值都会被当成0来处理
  • 如果对非数值应用位操作符，会先使用Number()将该值转换成数值再应用位操作，得到的结果是一个数值
//'|'表示按位或，一个整数与0按位或运算可以得到它本身，一个小数与0按位或运算可以得到取整效果
console.log( 1.3 | 0);//1
console.log( 1.8 | 0);//1
console.log( Infinity | 0);//0
console.log( -Infinity | 0);//0
console.log( NaN | 0);//0
console.log('12px' | 0);//0
console.log('12' | 0);//12

以下来源于w3shool:
ECMAScript 整数有两种类型，即有符号整数（允许用正数和负数）和无符号整数（只允许用正数）。在 ECMAScript 中，所有整数字面量默认都是有符号整数，这意味着什么呢？

有符号整数使用 31 位表示整数的数值，用第 32 位表示整数的符号，0 表示正数，1 表示负数。数值范围从 -2147483648 到 2147483647。

可以以两种不同的方式存储二进制形式的有符号整数，一种用于存储正数，一种用于存储负数。正数是以真二进制形式存储的，前 31 位中的每一位都表示 2 的幂，从第 1 位（位 0）开始，表示 20，第 2 位（位 1）表示 21。没用到的位用 0 填充，即忽略不计。例如，下图展示的是数 18 的表示法。

那在js中二进制和十进制如何转换呢？如下

console.log((18).toString(2));//"10010"
console.log(0b00000000000000000000000000010010);//18

// 十进制 => 二进制
let num = 10;
console.log(num.toString(2));
// 二进制 => 十进制
let num1 = 1001;
console.log(parseInt(num1, 2));

负数同样以二进制存储，但使用的格式是二进制补码。计算一个数值的二进制补码，需要经过下列3个步骤：

  1. 求这个数值绝对值的二进制码
  2. 求二进制反码，即将0替换成1，将1替换成0
  3. 得到的二进制反码加1

例如，要确定-18的二进制表示，首先必须得到18的二进制表示，如下所示：
0000 0000 0000 0000 0000 0000 0001 0010

接下来，计算二进制反码，如下所示：
1111 1111 1111 1111 1111 1111 1110 1101

最后，在二进制反码上加 1，如下所示：
1111 1111 1111 1111 1111 1111 1110 1101 +
0000000000000000000000000000 0001 =
1111 1111 1111 1111 1111 1111 1110 1110

因此，-18 的二进制表示即 1111 1111 1111 1111 1111 1111 1110 1110

ECMAScript会尽力向我们隐藏所有这些信息，在以二进制字符串形式输出一个负数时，我们看到的只是这个负数绝对值的二进制码前面加上了一个负号

var num = -18;
console.log(num.toString(2));//'-10010'

位运算符可以进行7种运算，包括按位非(NOT)、按位与(AND)、按位或(OR)、按位异或(XOR)、左移、有符号右移和无符号右移

js中的那些位运算

  • 按位或 |

对每对比特位执行或（OR）操作。只有 a 和 b 任意一位为1时，a | b 就是 1。如下表9 | 3 = 11

9 = 1 0 0 1
3 = 0 0 1 1
11 = 1 0 1 1

应用场景：

  1. 取整

对于一般的整数，返回值不会有任何变化。对于大于2的32次方的整数，大于32位的数位都会被舍去。如下例子中，1521156574878|0=738152094，因为1521156574878已经超出了最大范围2147483647，所以数值会发生巨大变化

function toInt(num) {
    return num | 0
}
console.log(toInt(1.8))        // 1
console.log(toInt(1.23232))    // 1
console.log(toInt(1532151156.015)) // 1532151156
console.log(toInt(1521156574878)) // 738152094
  1. 边界判断

假如我们有一个拖动事件，规定被拖动模块需要在容器内部运动，这时就有边界判断，这其中又包括上，下，左，右四种单一边界，同时还有类似上右，上左等叠加边界，如果我们需要记录这种状态，通过位运算要比使用if判断要简单一些，上右下左四种边界分别用1，2，4，8表示，代码如下：

let flag = 0;
if (pos.left < left) flag = flag | 8;
if (pos.right > right) flag = flag | 2;
if (pos.bottom > bottom) flag = flag | 4;
if (pos.top < top) flag = flag | 1;
switch(flag) {
    // 上
    case 1: 
    // 右
    case 2:
    // 右上
    case 3:
    // 下
    case 4:
    // 右下
    case 6:
    // 左
    case 8:
    // 左上
    case 9:
    // 左下
    case 12:
    // code
}

同理，假如我们有一系列控制开关，通过 a | b | c的形式要比 '{a: true, b: true, c: true}' 简单的多。

  • 按位与 &

对每对比特位执行与（AND）操作。只有 a 和 b 都为1时，a & b 就是 1。如下表9 & 3 = 1

9 = 1 0 0 1
3 = 0 0 1 1
1 = 0 0 0 1

由上表我们可以清晰的看出按位与的计算规则，由此可以引出一系列应用场景

  1. 判断奇偶

我们知道奇数的二进制最后一位必然为1，所以任意一个奇数 & 1 一定等于1。

// 判断奇偶
return number & 1 === 1
  1. 系统权限

业务场景：
我们假设某个管理系统有a, b, c, d四级权限，其中不同帐号分别有不同的权限（可能有1个或多个），例如admin 账户有a + b +c +d 四级权限，guest用户有b + c权限，那这时候应该怎么设计更简单一些呢？

按位与：是时候登场了！

基本思路：
我们把权限分别用0001, 0010, 0100, 1000表示（即最通俗的1，2，4，8），如果admin用户有a, b, c, d四种权限，则admin的权限为 1 | 2 | 4 | 8 = 15，而guest用户权限为 4 | 8 = 12, 则判断用户是否有某种权限可以如下判断

admin & 4 === 4
admin & 8 === 8
admin & 2 === 2
admin & 1 === 1

  • 按位异或 ^

对于每一个比特位，当两个操作数相应的比特位有且只有一个1时，结果为1，否则为0。

其运算法则相当于不带进位的二进制加法

9 = 1 0 0 1
3 = 0 0 1 1
10 = 1 0 1 0

应用场景：

  1. 切换变量0和1

假如我们通过某个条件来切换一个值为0或者1

function update(toggle) {
    num = toggle ? 1 : 0;
}

update(true);

// 通过异或我们可以这么写
num = num ^ 1;
  1. 交换两个变量的值(不用第三个变量)
let a = 5,
    b = 6;

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

// 还可以通过运算
a = a + b;
b = a - b;
a = a - b;

// es 6
[a, b] = [b, a]

原理剖析：a = a ^ b; b = a ^ b 相当与 b = a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a;

  1. 简单字符串加密
  const key = 313;
  function encryption(str) {
      let s = '';
      str.split('').map(item => {
        s += handle(item);
      })
      return s;
  }

  function decryption(str) {
    let s = '';
    str.split('').map(item => {
        s += handle(item);
    })
    return s;
  }

  function handle(str) {
      if (/\d/.test(str)) {
        return str ^ key;
      } else {
        let code = str.charCodeAt();
        let newCode = code ^ key;
        return String.fromCharCode(newCode);
      }
  }

  let init = 'hello world 位运算';
  let result = encryption(init);             // őŜŕŕŖęŎŖŋŕŝę乴軩窮
  let decodeResult = decryption(result);     // hello world 位运算

可以看到，我们利用字符串Unicode值的异或运算实现了一个简要的字符串加密效果。

ps: 上面代码仅为演示，实际解密时应该把key及解密密钥传进去。

  • 按位非 ～

对每一个比特位执行非（NOT）操作。NOT a 结果为 a 的反转（即反码）。

ps: 对任一数值 x 进行按位非操作的结果为 -(x + 1)。例如，~5 结果为 -6，~~ 5=~(-6)=-(-5)=5

负数存储采用的形式是二进制补码。计算数字二进制补码的步骤有三步：

1.确定该数字的非负版本的二进制表示（例如，要计算 -18的二进制补码，首先要确定 18 的二进制表示）

2.求得二进制反码，即要把 0 替换为 1，把 1 替换为 0（相当于～操作）

3.在二进制反码上加 1

我们可以看到一个数a取负相当于 ~a + 1, 即 -a = ~a + 1, 因此～a = -(a + 1)

应用场景：

  1. 取整 （位运算花样取整）
~~(-5.88) // -5
  1. 判断数组中某项是否存在
// 常用判断
if (arr.indexOf(item) > -1) {
    // code
}
// 按位非    ~-1 = - (-1 + 1)
if (~arr.indexOf(item)) {
    // code
}

按位移动操作符

按位移动操作符有两个操作数：第一个是要被移动的数字，而第二个是要移动的长度。移动的方向根据操作符的不同而不同。

按位移动会先将操作数转换为大端字节序顺序(big-endian order)的32位整数,并返回与左操作数相同类型的结果。右操作数应小于 32位，否则只有最低 5 个字节会被使用。

  • 左移 <<

该操作符会将第一个操作数向左移动指定的位数。向左被移出的位被丢弃，右侧用 0 补充。

例如 3 << 2 的运算图示如下：
3 = 0000 0000 0000 0000 0000 0000 0000 0011
12 = 0000 0000 0000 0000 0000 0000 0000 1100

ps: 对任一数值 x 进行左移n, 相当于十进制里的乘以10的倍数，在这儿是指

x * 2^n

应用场景：

rgb和16进制颜色转换

首先我们需要知道RGB与十六进制之间的关系，例如我们最常见的白色RGB表示为rgb(255, 255, 255), 十六进制表示为#FFFFFFF, 我们可以把十六进制颜色除
‘#’外按两位分割成一部分，即FF,FF,FF, 看一下十六进制的FF转为十进制是多少呢？没错，就是255!

了解了十六进制和RGB关系之后，我们就会发现RGB转十六进制方法就很简单了

  1. 将RGB的3个数值分别转为十六进制数，然后拼接，即 rgb(255, 255, 255) => '#' + 'FF' + 'FF' + 'FF'。
  2. 巧妙利用左移，我们把十六进制数值部分当成一个整数，即FFFFFF,我们可以理解为FF0000 + FF00 + FF, 如同我们上面解释，如果左移是基于十六进制计算的，则可以理解为FF << 4, FF << 2, FF, 而实际上我们转为二进制则变为 FF << 16，如下：
x * 16^4  = x * 2 ^ 16

了解了原理以后，代码如下：

function RGBToHex(rgb){
    // 取出rgb中的数值
    let arr = rgb.match(/\d+/g);
    if (!arr || arr.length !== 3) {
        console.error('rgb数值不合法');
        return
    }
    let hex = (arr[0]<<16 | arr[1]<<8 | arr[2]).toString(16);
    // 自动补全第一位
    if (hex.length < 6) {
        hex = '0' + hex;
    }
    return `#${hex}`;
}

  • 有符号右移 >>

该操作符会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃，拷贝最左侧的位以填充左侧。由于新的最左侧的位总是和以前相同，符号位没有被改变。所以被称作“符号传播”。

ps: 对任一数值 x 进行右移n, 相当于十进制里的除以10的倍数，在这里是指除以数之后取整

x / 2^n

应用场景：

十六进制转RGB

原理见上方RGB转十六进制

function hexToRGB(hex){
    if (!/^#([0-9a-fA-F]{3}){1,2}$/.test(hex)) {
        console.error('颜色不合法'); 
        return
    };
    // #f00 转为 #ff0000
    if (hex.length == 4) {
        hex = hex.replace(/([0-9a-fA-F])/g, '$1$1');
    };
    let num = hex.replace('#', '0x');
    let r = num >> 16;
    // 0xff = 255
    let g = num >> 8 & 0xff;
    let b = num  & 0xff;    
    return `rgb(${r},${g},${b})`;
}

  • 无符号右移 >>>

该操作符会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃，左侧用0填充。因为符号位变成了 0，所以结果总是非负的。（译注：即便右移 0 个比特，结果也是非负的。）

  • 应用场景总结

【1】乘法运算
利用左移(<<)来实现乘法运算

console.log(2 << 1);//4
console.log(3 << 1);//6
console.log(4 << 1);//8

【2】除法运算
利用有符号右移(>>)来模拟2的整除运算

console.log(2 >> 1);//1
console.log(5 >> 1);//2
console.log(8 >> 1);//4
console.log(9 >> 1);//4

【3】值互换
利用异或操作(^)可以实现值互换的效果

var a=10,b=9;
a ^= b, b ^= a, a ^= b;
console.log(a,b);//9,10

【4】小数取整
利用取两次按位非、与0按位或、与0按位异或、左移0位、右移0位都可以实现小数取整效果

console.log(~~3.1);//3
console.log(3.1|0);//3
console.log(3.1^0);//3
console.log(3.1<<0);//3
console.log(3.1>>0);//3

【5】开关
`位运算符可以用作设置对象属性的开关。假定某个对象有四个开关，每个开关都是一个变量。那么，可以设置一个四位的二进制数，它的每个位对应一个开关

var FLAG_A = 1; // 0001
var FLAG_B = 2; // 0010
var FLAG_C = 4; // 0100
var FLAG_D = 8; // 1000

上面代码设置A、B、C、D四个开关，每个开关分别占有一个二进制位
现在假设需要打开ABD三个开关，我们可以构造一个掩码变量

var mask = FLAG_A | FLAG_B | FLAG_D;
// 0001 | 0010 | 1000 => 1011

上面代码对ABD三个变量进行“或运算”，得到掩码值为二进制的1011

//“或运算”可以确保打开指定的开关
flags = flags | mask;
//“与运算”可以将当前设置中凡是与开关设置不一样的项，全部关闭
flags = flags & mask;
//“异或运算”可以切换（toggle）当前设置，即第一次执行可以得到当前设置的相反值，再执行一次又得到原来的值
flags = flags ^ mask;
//“否运算”可以翻转当前设置，即原设置为0，运算后变为1；原设置为1，运算后变为0
flags = ~flags;

【6】判断奇偶

奇数 & 1 = 1
偶数 & 1 = 0

题外话

想起之前小组内的一道算法题，题目是这样的：
1.一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
解题思路是：

/*因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
那么f(n-1)=f(n-2)+f(n-3)+...+f(1)

所以算法为：

function jumpFloorII(number){
    return 1<<(number-1);
}

WTF? 什么意思？
其实很简单，看下面过程

f(n)=f(n-1)+f(n-2)+...+f(1)
f(n-1)=f(n-2)+f(n-3)+...+f(1)
f(n) = 2*f(n-1) = 4 * f(n-2) = 8 * f(n-3) ..... = 2的(n-1)次方乘f(1),转为位运算即为 1 << (n - 1)

练习题：如何实现日历签到功能

  1. 怎么设计能使数据最少
  2. 每日签到应该怎么更新
  3. 怎么判断某天是否签到

ps: 作者码字不易，如果觉得本文对你有帮助，去给原文作者个赞吧，哈哈哈～～【传送门】

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,616评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,020评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,078评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,040评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,154评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,265评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,298评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,072评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,491评论 1赞 306
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,795评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,970评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,654评论 4赞 337
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,272评论 3赞 318
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,985评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,223评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,815评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,852评论 2赞 351