js中位运算的骚操作

按位操作符

按位操作符(Bitwise operators) 将其操作数(operands)当作32位的比特序列(由0和1组成),而不是十进制、十六进制或八进制数值。

运算符 用法 描述
按位与(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位整数

所有的按位操作符的操作数都会被转成补码(two’s complement)形式的有符号32位整数。补码形式是指一个数的负对应值(negative counterpart)(如 5和-5)为数值的所有比特位反转后,再加1。反转比特位即该数值进行’非‘位运算,也即该数值的反码。例如下面为整数314的二进制编码:

1
00000000000000000000000100111010

下面编码 ~314,即 314 的反码:

1
11111111111111111111111011000101

最后,下面编码 -314,即 314 的反码再加1:

1
11111111111111111111111011000110

补码保证了当一个数是正数时,其最左的比特位是0,当一个数是负数时,其最左的比特位是1。因此,最左边的比特位被称为符号位(sign bit)。

按位逻辑操作符

从概念上讲,按位逻辑操作符按遵守下面规则:

  • 操作数被转换成32位整数,用比特序列(0和1组成)表示。超过32位的数字会被丢弃。例如, 以下具有32位以上的整数将转换为32位整数:

    1
    2
    转换前: 11100110111110100000000000000110000000000001
    转换后: 10100000000000000110000000000001
  • 第一个操作数的每个比特位与第二个操作数的相应比特位匹配:第一位对应第一位,第二位对应第二位,以此类推。

  • 位运算符应用到每对比特位,结果是新的比特值。

  • &(按位与)

  • |(按位或)
  • ^(按位异或)
  • ~(按位非)

按位移动操作符

按位移动操作符有两个操作数:第一个是要被移动的数字,而第二个是要移动的长度。移动的方向根据操作符的不同而不同。
按位移动会先将操作数转换为大端字节序顺序(big-endian order)的32位整数,并返回与左操作数相同类型的结果。右操作数应小于 32位,否则只有最低 5 个字节会被使用。

注:Big-Endian:高位字节排放在内存的低地址端,低位字节排放在内存的高地址端,
又称为”高位编址”。
Big-Endian是最直观的字节序:

  • ①把内存地址从左到右按照由低到高的顺序写出;
  • ②把值按照通常的高位到低位的顺序写出;
  • ③两者对照,一个字节一个字节的填充进去。

<< (左移)

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

1
2
3
     9 (base 10): 00000000000000000000000000001001 (base 2)
--------------------------------
9 << 2 (base 10): 00000000000000000000000000100100 (base 2) = 36 (base 10)

9 << 2的值为36。

>> (有符号右移)

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

1
2
3
     9 (base 10): 00000000000000000000000000001001 (base 2)
--------------------------------
9 >> 2 (base 10): 00000000000000000000000000000010 (base 2) = 2 (base 10)

9 >> 2得到 2。

1
2
3
     -9 (base 10): 11111111111111111111111111110111 (base 2)
--------------------------------
-9 >> 2 (base 10): 11111111111111111111111111111101 (base 2) = -3 (base 10)

-9 >> 2得到 -3。

>>> (无符号右移)

该操作符会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃,左侧用0填充。因为符号位变成了 0,所以结果总是非负的。

对于非负数,有符号右移和无符号右移总是返回相同的结果。例如 9 >>> 2 和 9 >> 2 一样返回 2。

但是对于负数却不尽相同。 -9 >>> 2 产生 1073741821 这和 -9 >> 2 不同

标志位与掩码

位运算经常被用来创建、处理以及读取标志位序列——一种类似二进制的变量。虽然可以使用变量代替标志位序列,但是这样可以节省内存(1/32)。

例如,有 4 个标志位:

  • 标志位 A:我们有 ant
  • 标志位 B:我们有 bat
  • 标志位 C:我们有 cat
  • 标志位 D:我们有 duck

标志位通过位序列 DCBA 来表示。当一个位被置位 (set) 时,它的值为 1 。当被清除 (clear) 时,它的值为 0 。例如一个变量 flags 的二进制值为 0101:

1
var flags = 5;   // 二进制 0101

这个值表示:

  • 标志位 A 是 true (我们有 ant);
  • 标志位 B 是 false (我们没有 bat);
  • 标志位 C 是 true (我们有 cat);
  • 标志位 D 是 false (我们没有 duck);

因为位运算是 32 位的, 0101 实际上是 00000000000000000000000000000101。因为前面多余的 0 没有任何意义,所以他们可以被忽略。

掩码 (bitmask) 是一个通过与/或来读取标志位的位序列。典型的定义每个标志位的原语掩码如下:

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

新的掩码可以在以上掩码上使用逻辑运算创建。例如,掩码 1011 可以通过 FLAG_A、FLAG_B 和 FLAG_D 逻辑或得到:

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

某个特定的位可以通过与掩码做逻辑与运算得到,通过与掩码的与运算可以去掉无关的位,得到特定的位。例如,掩码 0100 可以用来检查标志位 C 是否被置位:

1
2
3
4
// 如果我们有 cat
if (flags & FLAG_C) { // 0101 & 0100 => 0100 => true
// do stuff
}

一个有多个位被置位的掩码表达任一/或者的含义。例如,以下两个表达是等价的:

1
2
3
4
5
// 如果我们有 bat 或者 cat 至少一个
// (0101 & 0010) || (0101 & 0100) => 0000 || 0100 => true
if ((flags & FLAG_B) || (flags & FLAG_C)) {
// do stuff
}
1
2
3
4
5
// 如果我们有 bat 或者 cat 至少一个
var mask = FLAG_B | FLAG_C; // 0010 | 0100 => 0110
if (flags & mask) { // 0101 & 0110 => 0100 => true
// do stuff
}

可以通过与掩码做或运算设置标志位,掩码中为 1 的位可以设置对应的位。例如掩码 1100 可用来设置位 C 和 D:

1
2
3
// 我们有 cat 和 duck
var mask = FLAG_C | FLAG_D; // 0100 | 1000 => 1100
flags |= mask; // 0101 | 1100 => 1101

可以通过与掩码做与运算清除标志位,掩码中为 0 的位可以设置对应的位。掩码可以通过对原语掩码做非运算得到。例如,掩码 1010 可以用来清除标志位 A 和 C :

1
2
3
// 我们没有 ant 也没有 cat
var mask = ~(FLAG_A | FLAG_C); // ~0101 => 1010
flags &= mask; // 1101 & 1010 => 1000

如上的掩码同样可以通过 ~FLAG_A & ~FLAG_C 得到(德摩根定律)

1
2
3
// 我们没有 ant 也没有 cat
var mask = ~FLAG_A & ~FLAG_C;
flags &= mask; // 1101 & 1010 => 1000

标志位可以使用异或运算切换。所有值为 1 的位可以切换对应的位。例如,掩码 0110 可以用来切换标志位 B 和 C:

1
2
3
4
5
// 如果我们以前没有 bat ,那么我们现在有 bat
// 但是如果我们已经有了一个,那么现在没有了
// 对 cat 也是相同的情况
var mask = FLAG_B | FLAG_C;
flags = flags ^ mask; // 1100 ^ 0110 => 1010

最后,所有标志位可以通过非运算翻转:

1
2
// entering parallel universe...
flags = ~flags; // ~1010 => 0101

转换片段

将一个二进制数的 String 转换为十进制的 Number:

1
2
3
var sBinString = "1011";
var nMyNumber = parseInt(sBinString, 2);
alert(nMyNumber); // 打印 11

将一个十进制的 Number 转换为二进制数的 String:

1
2
3
var nMyNumber = 11;
var sBinString = nMyNumber.toString(2);
alert(sBinString); // 打印 1011

自动化掩码创建

如果你需要从一系列的 Boolean 值创建一个掩码,你可以:

1
2
3
4
5
6
7
8
9
10
11
function createMask () {
var nMask = 0, nFlag = 0, nLen = arguments.length > 32 ? 32 : arguments.length;
for (nFlag; nFlag < nLen; nMask |= arguments[nFlag] << nFlag++);
return nMask;
}
var mask1 = createMask(true, true, false, true); // 11, i.e.: 1011
var mask2 = createMask(false, false, true); // 4, i.e.: 0100
var mask3 = createMask(true); // 1, i.e.: 0001
// etc.

alert(mask1); // 打印 11

逆算法:从掩码得到布尔数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function arrayFromMask (nMask) {
// nMask 必须介于 -2147483648 和 2147483647 之间
if (nMask > 0x7fffffff || nMask < -0x80000000) {
throw new TypeError("arrayFromMask - out of range");
}
for (var nShifted = nMask, aFromMask = []; nShifted;
aFromMask.push(Boolean(nShifted & 1)), nShifted >>>= 1);
return aFromMask;
}

var array1 = arrayFromMask(11);
var array2 = arrayFromMask(4);
var array3 = arrayFromMask(1);

alert("[" + array1.join(", ") + "]");
// 打印 "[true, true, false, true]", i.e.: 11, i.e.: 1011

位运算的应用

按位非~判断索引存在

一般都是用“str.indexOf(‘test’) > -1”这种形式来判断字符串str中是否包含”test”字符串,现在可以利用位运算符“~”:“~str.indexOf(‘test’)”,包含时返回非0数字,不包含时则返回0。

时间对比:
p-1.png

其实两者执行性能差距不大。

再来简单介绍下用~判断索引的原理,核心:

1
~-1 === 0

-1在内存的表示的二进制符号全为1,按位非之后就变成了0. 由此也说明了-1在内存的表示为:0000…0001,第一位0表示符号位为正,如果是-1的话符号位为负用1表示1000…0001,这个是-1的原码,然后符号位不动,其余位取反变成1111…1110,这个就是-1的反码表示,反码再加1就变成了1111…1111,这个就是-1的补码,负数在内存里面(机器数)使用补码表示,正数是用原码。所以全部都是1的机器数按位非之后就变成了全为0。剩下的其它所有数按位非都不为0,所以利用这个特性可以用来做indexOf的判断,我个人已经习惯这种写法,因为感觉更方便并且代码看起来更简洁。

判断数字奇偶性:&

1
2
奇数 & 1 = 1;
偶数 & 1 = 0;


1
2
3
4
5
var num1 = 10,
num2 = 13;

console.log(num1 & 1); // 0
console.log(num2 & 1); // 1

取整(舍弃小数部分):~~/>>/<</>>>/|

注:>>>不可用于负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 正数
console.log(~~5.21); // 5
console.log(5.21 >> 0); // 5
console.log(5.21 << 0); // 5
console.log(5.21 | 0); // 5
console.log(5.21 >>> 0); // 5

// 负数
console.log(~~-5.21); // -5
console.log(-5.21 >> 0); // -5
console.log(-5.21 << 0); // -5
console.log(-5.21 | 0); // -5
console.log(-5.21 >>> 0); // 4294967291,所以不可使用>>>对负数进行取整

// 字符串正数
console.log(~~'5.21'); // 5
console.log('5.21' >> 0); // 5
console.log('5.21' << 0); // 5
console.log('5.21' | 0); // 5
console.log('5.21' >>> 0); // 5

// 字符串负数
console.log(~~'-5.21'); // 5
console.log('-5.21' >> 0); // 5
console.log('-5.21' << 0); // 5
console.log('-5.21' | 0); // 5
console.log('-5.21' >>> 0); // 4294967291,所以不可使用>>>对字符串负数进行取整

// 空字符串
console.log(~~''); // 0 同其他

// boolean
console.log(~~true); // 1 同其他
console.log(~~false); // 0 同其他

// undefined
console.log(~~undefined); // 0 同其他

// null
console.log(~~null); // 0 同其他

// NaN
console.log(~~NaN); // 0 同其他

>>实际上是一个快速的Math.floor()函数,速度有提升。

经典题,数字交换

要求不能使用额外的变量或内容空间来交换两个整数的值。使用异或位运算可以达到这个目的。

1
2
3
4
5
6
7
8
9
10
11
var a = 1,
b = 2;

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

console.log(a, b); // 2 1

// 变态版
a = (a ^ b) ^ a = a ^ a ^ b = 0 ^ b = b;

为什么a ^ a = 0, b ^ b = 0呢?

1
2
3
4
  01011010
^ 10010110
-----------
11001100

异或的运算过程可以当作把两个数加起来,然后进位去掉,0 + 0 = 0,1 + 0 = 1,1 + 1 = 0。这样就很好记。所以a ^ a在所有二进制位上,要么同为0,要么同为1,相加结果都为0,最后就为0.

异或也常被用于加密。

使用按位与&去掉高位

去操作数的高位,只保留低位,例如有a, b两个数:

1
2
let a = 0b01000110; // 十进制为70
let b = 0b10000101; // 十进制为133

现在认为他们的高位是没用的,只有低4位是有用的,即最后面4位,为了比较a,b后4位的大小,可以这样比较:

1
a & 0b00001111 < b & 0b00001111 // true

a, b的前4位和0000与一下之后就都变成0了,而后四位和1111与一下之后还是原来的数。这个实际的作用是有一个数字它的前几位被当作A用途,而后几位被用当B用途,为了去掉前几位对B用途的影响,就可以这样与一下。

另外一个例子是子网掩码,假设现在我是网络管理员,我能够管理的IP地址是从192.168.1.0到192.168.1.255,即只能调配最后面8位。现在把这些IP地址分成6个子网,通过IP地址进行区分,由于6等于二进制的110,所以最后面8位的前3位用来表示子网,而后5位用来表示主机(即总的主机数的范围为00001 ~ 11111, 共30个)。当前网络的子网掩码取为255.255.255.111 00000即255.255.255.224,假设某台主机的IP地址为192.168.1.120,现在要知道它处于哪个子网,可以用它IP地址与子网掩码与一下:120 & 224 = 96 = 0b 011 00000,就知道它所在的子网为011即3号子网。

这个是保留高位去掉低位的例子,刚好与上面的例子相反。

使用按位|构造属性集

Google地图中有个骚操作,利用位操作来判断位置,即边界判断。

边界判断的例子——要在当前鼠标的位置往上弹一个悬浮框,如下图左所示,但是当鼠标比较靠边的时候就会导致悬浮框超出边界了。

为此,需要做边界判断,总共有3种超出情况:右、上、左,并且可能会叠加,如鼠标在左上角的时候会导致左边和上面同时超出。需要记录超出的情况进行调整,用001表示右边超出,010表示上方超出,100表示左边超出,如下代码计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//右边超出
if(pos.right < maxLen) posFlag |= 1;
//上面超出
if(pos.top < maxLen) posFlag |= 2;
//左边超出
if(pos.left < maxLeftLen) posFlag |= 4;
//对超出的情况进行处理,代码略
switch(posFlag){
case 1: //右
case 2: //上
case 3: //右上
case 4: //左
case 6: //左上
}

如果左边和上面同时超出,那么通过或运算2 | 4 = 6,得到6 = 0b110. 就知道了超出的情况,这样的代码相对于在if里面写两个判断要好一些。

使用按位与&进行标志位判断

现在有个后台管理系统,操作权限分为一级、二级、三级管理员,其中一级管理员拥有最高的权限,二、三级较低,有些操作只允许一、二级管理员操作,有些操作只允许一、三级管理员操作。现在已经登陆的某权限的用户要进行某个操作,要用怎样的数据结构能很方便地判断他能不能进行这个操作呢?

我们用位来表示管理权限,一级用第3位,二级用第2位,三级用第1位,即一级的权限表示为0b100 = 4,二级权限表示为0b010 = 2,三级权限表示为0b001 = 1。如果A操作只能由一级和二级操作,那么这个权限值表示为6 = 0b110,它和一级权限与一下:6 & 4 = 0b110 & 0b100 = 4,得到的值不为0,所以认为有权限,同理和二级权限与一下6 & 2 = 2也不为0,而与三级权限与一下6 & 1 = 0,所以三级没有权限。这里标志位的1表示打开,0表示关闭。

这样的好处在于,我们可以用一个数字,而不是一个数组来表示某个操作的权限集,同时在进行权限判断的时候也很方便。

不使用加减乘除来做加法

(经常用来考察对位运算的掌握情况)

不能用加减乘除,意思就是要你用位运算进行计算。以实际例子说明,如a = 81 = 0b1010001,b = 53 = 0b0110101。通过异或运算,我们发现异或把两个数相加但是不能进位,而通过与运算能够知道哪些位需要进位,如下所示:

1
2
3
4
5
6
7
8
9
  1010001
^ 0110101
---------
1100100

1010001
& 0110101
---------
0010001

把通过与运算得到的值向左移一位,再和通过异或得到的值相加,就相当于实现了进位,这个应该不难理解。为了实现这两个数的相加可以再重复这个过程:先异或,再与,然后进位,直到不需要再进位了就加完了。所以不难写出以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function addByBit(a, b) {
if (b === 0) {
return a;
}
// 不用进位的相加
let c = a ^ b;
// 记录需要进位的
let d = a & b;
d = d << 1;
// 继续相加,直到d进位为0
return addByBit(c, d);
}

let ans = addByBit(5, 8);
console.log(ans);

位运算还经常用于生成随机数、哈希,例如Chrome对字符串进行哈希的算法是这样的:

1
2
3
4
5
6
uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
running_hash += c;
running_hash += (running_hash << 10);
running_hash ^= (running_hash >> 6);
return running_hash;
}

不断对当前字符串的ASCII值进行累加运算,里面用到了异或,左移和右移。

位掩码来判断选项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 定义所有的可选项
var OPTION_A = 1,
OPTION_B = 2,
OPTION_C = 4,
OPTION_D = 8,
OPTION_E = 16;

// 包含选项 A、B、D
var options = OPTION_A | OPTION_B | OPTION_D; // 1 | 10 | 1000 -> 1011

// 判断选项是否被包含在 options 中
options & OPTION_A // 1011 & 1 -> 0001, true
options & OPTION_B // 1011 & 10 -> 0010, true
options & OPTION_C // 1011 & 110 -> 0, false
options & OPTION_D // 1011 & 1000 -> 1000, true
options & OPTION_E // 1011 & 10000 -> 0, false

相关链接