JavaScript位运算指南

3,317 阅读10分钟

位运算

背景

为什么要做js位运算呢?

  • 因为最近在学习hash算法,里面用到了大量的位运算

  • 另外网上也找了很多资料,但大都比较片面,没有说明特殊情况时的处理,换几组数据计算结果就出错。

重温整数

ECMAScript 整数有两种类型,即:

  • 有符号整数(允许用正数和负数)
  • 无符号整数(只允许用正数) 在 ECMAScript 中,所有整数字面量默认都是有符号整数,这意味着什么呢?

有符号整数使用 31 位表示整数的数值,用第 32 位表示整数的符号,0 表示正数,1 表示负数。

数值范围从 -2147483647 到 2147483647。

位运算会把二进制数限制在32位,超出部分会被舍弃

调试位运算常用的几个方法

toString(2)

转换成2进制字符串

var a = 1732584193;
a.toString(2); // 1100111010001010010001100000001

parseInt('11001', 2)

将2进制字符串转换成10进制数

parseInt('11001', 2) // 25

padStart(32, '0')

字符串总长度,左边不足位数补0

'1100000001'.padStart(32, 0) // 00000000000000000000001100000001

源码、反码、补码

源码

将数字转换成的2进制数, 最左边表示符号位,1负数,0正数

5 源码: 0101
-10 源码:11010

反码

正数的反码与其原码相同

负数的反码,除符号位外,其他位取反

5 
源码:0101 
反码:0101

-10
源码:11010 
反码:10101

补码

正整数的补码与其原码相同

负整数的补码,取反码+1

5
源码:0101
补码:0101

-10
源码:11010
补码:10110

ok,现在开始正题

位运算符

  • 非(~)
  • 与(&)
  • 或(|)
  • 异或(^)
  • 带符号左移(<<)
  • 带符号右移(>>)
  • 无符号右移(>>>)

位运算符:非(~)

运算步骤:

  1. 将该数字取负数
  2. 然后减1
~25 // -26

过程:

  • 25取负:-25
  • 减1:-26
~1  // -2
~-1 // 0
~100 // -101
~-100 // 99

位运算符:与(&)

运算步骤:

  1. 把两个数转换成2进制补码
  2. 相同位置进行比较(同为1,结果为1,否则为0)
  3. 如果计算结果是负数,还要再做补码处理

如果位数不够,正数左边补0,负数补1

正正运算

10 & 3 // 2

过程:

  • 10 补码:1010
  • 3 补码: 0011
  • 结果:0010,即 2

正负运算(1)

14 & -13 // 2

过程:

  • 14 补码:01110(补一位符号位)
  • -13 源码:11101,补码:10011
  • 与运算:00010,即 2

正负运算(2)

88 & -19 // 72

过程:

  • 88 补码:01011000(补一位符号位)
  • -19 源码:110011,补码:101100
  • 01011000 & 101100
  • 负数(101100)位数不够,左边补1,即11101100
  • 也就是 01011000 & 11101100
  • 结果为:01001000,即:72

负负运算

-12 & -5 // -16

过程:

  • -12 补码:10100
  • -5 补码: 11011
  • 与运算: 10000
  • 结果为负,再取一次补码: 110000: -16

练习

3 & 7
-21 & 16
-271733879 & -1732584194
1125899778533470 & 812930
20 & 0xF
48192342 & 0xFFFF

位运算符:或(|)

运算步骤:

  1. 把两个数字转换成2进制补码
  2. 相同位置进行比较(有一个是1,结果即为1)
  3. 如果计算结果是负数,还要再做补码处理

正正运算

10 | 3 // 11

过程:

  • 10 源码:1010
  • 3 源码:0011
  • 结果:1011,即 11

正负运算

10 | -3 // -1

过程:

  • 10补码:01010
  • -3补码:11101
  • 或运算:11111
  • 结果为负,再取码:10001,即:-1

负负运算

-15 | -21 // -5

过程:

  • -15 补码:110001
  • -21 补码:101011
  • 或运算:111011
  • 结果为负再取补码:10101,即:-5

练习

15 | 20
40 | -14
-271733879 | 1732584193
(-271733879 & -1732584194) | (~-271733879 & 271733878)

位运算符:异或(^)

运算步骤:

  1. 把两个数转换成2进制补码
  2. 相同位置进行比较(必须是0和1或者1和0,结果才为1)
  3. 如果结果为负,再取补码

正正异或

10 ^ 3 // 9

过程:

  • 10 补码:1010
  • 3 补码:0011
  • 结果:1001,即 9

正负异或

10 ^ -3 // -9

过程:

  • 10 补码: 01010
  • -3 补码:11101
  • 异或运算:10111
  • 结果为负,再取补码:11001,即-9

负负异或

-10 ^ -3 // 11

过程:

  • -10 补码:10110
  • -3 补码:11101
  • 异或运算:01011,即:11

练习

5 ^ 8
-10 ^ 9
-13 ^ -20
-271733879 ^ -1732584194 ^ 271733878

位运算符:带符号左移(<<)

运算步骤:

  1. 把数字转换成2进制补码
  2. 左移指定位数,右边补0
  3. 如果结果未负数,再取补码

超过32位的部分舍弃

正数左移

1 << 2 // 补码:00000001 左移2位, 即 00000100,结果为:4
5 << 3 // 补码:00000101 左移3位, 即 00101000,结果为:40 

可以看出,正数带符号左移,即 a << n,其实是 a * 2的n次幂

负数左移

-3 << 4
  • -3 补码:101
  • 左移4位 1010000
  • 标志位为负,取补码:1110000,即-48
-6 << 3  // 1010 << 3 等于 1010000,取补码,1110000 即:-48
-11 << 4 // 10101 << 4 等于 101010000,取补码,110110000 即:-176

边缘情况

情况1:正数变负数

1732584193 << 2  // -1659597820

计算过程

  • 1732584193转换成2进制源码:1100111010001010010001100000001(31位)
  • 左移2位,补2个0:110011101000101001000110000000100(33位)
  • 移除左边多余的1位:10011101000101001000110000000100(32位)
  • 变为负数,取补码:11100010111010110111001111111100
  • 即:-1659597820

情况2:负数变正数

-1732584193 << 2  // 1659597820

计算过程

  • -1732584193转换成2进制:11100111010001010010001100000001(32位)
  • 负数,取补码:10011000101110101101110011111111(32位)
  • 左移2位:1001100010111010110111001111111100(34位)
  • 多余部分舍弃:01100010111010110111001111111100(32位)
  • 符号位为正,无需再补码,即:1659597820

练习

1 << 32 
1 << 33 
1 << 40
2147483648 << 2
1732584193 << 6

位运算符:带符号右移(>>)

运算步骤:

  1. 取数字二进制补码
  2. 右移指定位数,左边补位与符号位一致
  3. 多余位被舍弃
  4. 如果计算结果为负,再取补码

正数右移

5 >> 1 // 0101 右移1位 0010,即 2
1 >> 2 // 0001 右移1位 0000,即 0

正数右移比较简单,移出的内容直接舍弃即可,左边用0补充

负数右移

-5 >> 2 // -2

分析:

  • -5 补码:1011
  • 右移2位:1110
  • 结果为负,取补码:1010,即-2

练习

5 + 64 >> 9
1732584193 >> 4

位运算符:无符号右移(>>>)

运算步骤:

  1. 把数字转换成32位2进制补码
  2. 连同符号位,右移动指定的位数
  3. 向右被移出的位被丢弃,左侧用0填充

因为符号位变成了 0,所以结果总是正的

正数右移

正数时候 >> 和 >>> 结果是一样的

5 >> 2 // 101 右移2位 001 即:1
5 >>> 2 // 101 右移2位 001 即:1

负数右移

-5 >>> 2 // 1073741822

过程:

  • -5 源码: 10000000 00000000 00000000 00000101
  • 补码:11111111 11111111 11111111 11111011
  • 右移两位:00111111 11111111 11111111 11111110
  • 转换成十进制即为:1073741822

问题:为什么这个要补满32位,而之前的运算都没有?

因为之前的运算,正数补的都是0,负数虽然补1,但计算后要做补码,补位的数最终不影响计算

而无符号右移,则会影响运算。所以需要补全

练习

-23 >>> 2
45678765 >>> 31

关于位运算的核心思路

  • 运算前要取补码
  • 运算结果导致负数,再取一次补码

以上内容都是个人收集、以及多次尝试整理的。

因为网上看到的很多文章计算方式都不对,虽然举的例子没问题,但几组数字就计算错误。

特此整理了该篇文章,与大家共同学习