Skip to content

深入理解按位操作符

Published:

按位操作符(Bitwise operators) 的计算主要用在二进制中,虽然平时很少有机会用到按位操作符,但不得不承认,在某些时候,这些操作符能够给我们提供很好的解决方案。

1. 概述

按位操作符(Bitwise operators) 的计算主要用在二进制中,虽然平时很少有机会用到按位操作符,但不得不承认,在某些时候,这些操作符能够给我们提供很好的解决方案。

下面介绍操作符时,也会提供一些比较经典的例子,来看看它们是如何巧妙地解决问题的吧。

2. 正文

2.1 二进制

本文假设你知道计算机中用二进制数来存储,计算数字,并且熟悉二进制数的表示方法。

讲解位操作符之前,先简单讲一下真值、原码、反码和补码。

2.1.1 真值

我们表示自然数包括正数,负数和 0,下面是 1 和-1 的二进制表示:

+ 00000001 # +1
- 00000001 # -1

2.1.2 原码

但是计算机只能存储 0 和 1,不能存储正负,所以一个数的最高位存放符号,正数为 0,负数为 1,用后面七位来表示真值的绝对值:

0 0000001 # +1
1 0000001 # -1

由于10000000表示为 -0 ,这个没有意义,所以这个数字被用来表示 -128,所以负数就比整数多一个。

2.1.3 反码

反码的表示方法是:正数不变,负数是在其原码的基础上,符号位不变,其余位取反:

0 0000001 # +1
1 1111110 # -1

2.1.4 补码

补码的作用主要是为了简化运算,将减法变为加法而发明的数学表示法,其表示方法是:正数不变,负数是在其反码的基础上+1:

0 0000001 # +1
1 1111111 # -1

2.1.5 最后

[+1] = [0000 0001]原
     = [0000 0001]反
     = [0000 0001]补
--------------------
[-1] = [1000 0001]原
     = [1111 1110]反
     = [1111 1111]补

2.2. 按位逻辑操作符

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

下面开始讲解各种位操作符。

注意:

前面提到操作会被转换成 32 位整数,但为了简化,将使用 8 位整数来演示运算过程。

2.2.1 AND(与)

对每一对比特位执行与(AND)操作。只有 a 和 b 都是 1 时,a AND b 才是 1。与操作的真值表如下:

aba AND b
000
010
100
111

下面展示11 & 14的运算过程:

11 = 0000 1011
14 = 0000 1110
     0000 1010 = 10

注意:

例子 1(判断一个数的奇偶):

// n & 1 === 0
console.log(2 & 1) // 0
console.log(3 & 1) // 1
/*
原因:所有偶数的最低位都是0,所有奇数的最低位都是1。
实例1:
	16 = 10000
	1 =  00001
	     00000 = 0
实例2:
	15 = 1111
	1 =  0001
	     0001 = 1
*/

例子 2(判断一个数是否为 2 的整数幂):

// n & (n-1) === 0
console.log(4 & (4 - 1)) // 0
console.log(5 & (5 - 1)) // 4
/*
原因:如果是2的幂,n 一定是 100...,而 n-1 一定是 111...
实例1:
	16 = 10000
	15 = 01111
	     00000 = 0
实例1:
	15 = 1111
	14 = 1110
	     1110 = 14
*/

2.2.2 OR(或)

对每一对比特位执行或(OR)操作。只有 a 或者 b 中至少有一位是 1 时, a OR b 才为 1。或操作的真值表:

aba OR b
000
011
101
111

下面展示11 | 14的运算过程:

11 = 0000 1011
14 = 0000 1110
     0000 1111 = 15

注意:

2.2.3 XOR(异或)

对每一对比特位执行异或(XOR)操作。当 a 和 b 不相同时,a XOR b 的结果为 1。异或操作真值表:

aba XOR b
000
011
101
110

下面展示11 ^ 14的运算过程:

11 = 0000 1011
14 = 0000 1110
     0000 0101 = 5

注意:

例子 1(不用临时变量交换两个数):

var a = 10,
  b = 20
a ^= b
b ^= a
a ^= b
console.log(a, b) // 20,10
/*
原因(公式):
	20 ^ 10 = 30 # c = a ^ b
	30 ^ 20 = 10 # b = c ^ a
	30 ^ 10 = 20 # a = c ^ b
实例:
	a = 01010
	b = 10100
	c = 11110 # a ^ b的结果,其中的1是 a 和 b 中不同的部分
	d = 01010 # b ^ c的结果,有没有发现和a是一样的
	e = 10100 # c ^ d的结果,有没有发现是b是一样的

	a = a ^ b # 得到c 11110
	b = b ^ a # 得到d 01010
	a = a ^ b # 得到e 10100
*/

例子 2(找到数组中出现奇数次的元素):

// 一个非空数组,只有一个元素出现奇数次,其余出现偶数次,找出那个元素:
var arr = [1, 1, 2, 3, 3]
var res = 0
for (var i = 0; i < arr.length; i++) {
  res ^= arr[i]
}
console.log(res) // 2
/*
   任何一个数字异或它自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每一个数字,
   那么最终的结果刚好是那个只出现奇数次的数字,因为那些出现偶数次的数字全部在异或中抵消掉了。
*/

2.2.4 NOT(非)

对每一个比特位执行非(NOT)操作。NOT a 结果为 a 的反转(即反码)。非操作的真值表:

aNOT a
01
10

下面展示~11的运算过程:

11 = [0000 1011‬]原
   = [0000 1011‬]反
   = [‭0000 1011]补 # 将操作数转成补码
 -----------------------------
     [‭0000 1011]补
   = [1111 0100]补 # 然后按位取反
 -----------------------------
     [1111 0100]补
   = [1111 0011]反
   = [1000 1100]原 # 转成原码
   = -12

接着展示~-11的运算过程:

-11 = [1000 1011‬]原
    = [1111 0100‬]反
    = [‭1111 0101]补 # 将操作数转成补码
 -----------------------------
      [‭1111 0101]补
    = [0000 1010]补 # 然后按位取反
 -----------------------------
      [0000 1010]补
    = [0000 1010]反
    = [0000 1010]原 # 转成原码
    = 10

注意:

2.3 按位移动操作符

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

按位移动会先将操作数转换为高位字节顺序的 32 位整数,并返回与左操作符相同的类型。右操作数小于 32 位,否则只有最低 5 个字节会被使用。

2.3.1 <<(左移)

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

下面展示11<<2的运算过程:

11 = [0000 1011]原
   = [0000 1011]反
   = [0000 1011]补
---------------------------------
      0000 1011
   00 0010 1100 # 向左移2位,用0补充
      1101 0100 # 被移出的位被丢弃
---------------------------------
     [1101 0100]补
   = [1101 0011]反
   = [1010 1100]原 # 转成原码
   = -44

接着是-11<<2的运算过程:

11 = [1000 1011]原
   = [1111 0100]反
   = [1111 0101]补
---------------------------------
      1111 0101
   11 1101 0100 # 向左移2位,用0补充
      1101 0100 # 被移出的位被丢弃
---------------------------------
     [1101 0100]补
   = [1101 0011]反
   = [1010 1100]原 # 转成原码
   = -44

注意:

例子:

// 1.获得 int 型最大值
console.log(~(1 << 31)) // 2147483647
// 2.获得 int 型最小值
console.log(1 << 31) // -2147483648
// 3.乘以2的m次方
console.log(1 << 10, 1 * Math.pow(2, 10)) // 1024,1024

2.3.2 >>(有符号右移)

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

下面展示11>>2的运算过程:

11 = [0000 1011]原
   = [0000 1011]反
   = [0000 1011]补
---------------------------------
      0000 1011
      0000 0010 11 # 向右移2位,填充最左侧的值
      0000 0010 # 被移出的位被丢弃
---------------------------------
     [0000 0010]补
   = [0000 0010]反
   = [0000 0010]原 # 转成原码
   = 2

接着是-11>>2的运算过程:

11 = [1000 1011]原
   = [1111 0100]反
   = [1111 0101]补
---------------------------------
      1111 0101
      1111 1101 01 # 向右移2位,填充最左侧的值
      1111 1101 # 被移出的位被丢弃
---------------------------------
     [1111 1101]补
   = [1111 1100]反
   = [1000 0011]原 # 转成原码
   = -3

例子:

// 1.求两个整数的平均值(结果有小数点时抛弃小数点)
console.log(1 + 4>> 1 ) // 2
// 2.除以2的m次方
console.log( 1 >> 10, 1 * Math.pow(2,10) ) // 1024,1024

2.3.3 >>>(无符号右移)

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

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

而对于负数却不尽相同,下面展示-11>>>2的运算过程(这里需要用到的位数较多,所以用 32 位整数演示):

-11 = [‭1000 0000 0000 0000 0000 0000 0000 1011]原
    = [‭1111 1111 1111 1111 1111 1111 1111 0100]反
    = [‭1111 1111 1111 1111 1111 1111 1111 0101]补
-----------------------------------------------------
       ‭1111 1111 1111 1111 1111 1111 1111 0101
       0011 1111 1111 1111 1111 1111 1111 1101 01 # 向右移2位,左侧填充0
       0011 1111 1111 1111 1111 1111 1111 1101 # 被移出的位被丢弃
-----------------------------------------------------
      [0011 1111 1111 1111 1111 1111 1111 1101]补
    = [0011 1111 1111 1111 1111 1111 1111 1101]补
    = [0011 1111 1111 1111 1111 1111 1111 1101]原 # 转成原码
    = 1073741821

3. 参考资料


作者 : 4Ark

地址 : https://4ark.me/posts/2019-03-15-learn-bitwise-operators/

来源 : https://4ark.me

著作权归作者所有,转载请联系作者获得授权。