91

深入理解按位操作符 - 4Ark

 5 years ago
source link: https://4ark.me/post/3953655a.html?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

深入理解按位操作符

2019-03-15

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

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

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

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位整数，用比特序列（0和1组成）表示。超过32位的数字会被丢弃。

  • 第一个操作数的每个比特位与第二个操作数的相应比特位匹配：第一位对应第一位，第二位对应第二位，以此类推。

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

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

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

2.2.1 AND（与）

对每一对比特位执行与（AND）操作。只有 a 和 b 都是 1 时，a AND b 才是 1。与操作的真值表如下：

a b a AND b
0 0 0
0 1 0
1 0 0
1 1 1

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

11 = 0000 1011
14 = 0000 1110
     0000 1010 = 10
  • 任何数和 0 进行 AND 都为0：x & 0 = 0。
  • 任何数和 -1 进行 AND 都为自身：x & -1 = x。

例子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。或操作的真值表：

a b a OR b
0 0 0
0 1 1
1 0 1
1 1 1

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

11 = 0000 1011
14 = 0000 1110
     0000 1111 = 15
  • 任何数和 0 进行 OR 都为自身：x | 0 = x。
  • 任何数和 -1 进行 OR 都为 -1：x | -1 = -1。

2.2.3 XOR（异或）

对每一对比特位执行异或（XOR）操作。当 a 和 b 不相同时，a XOR b 的结果为 1。异或操作真值表：

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

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

11 = 0000 1011
14 = 0000 1110
     0000 0101 = 5
  • 任何数和 0 进行 XOR 都为自身：x ^ 0 = x。
  • 任何数和 -1 进行 OR 都为 ~x：x | -1 = ~x。

例子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 的反转（即反码）。非操作的真值表：

a NOT a
0 1
1 0

下面展示~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
  • 对任何数 x 进行 NOT 操作的结果为 -(x + 1)，~x = -(x+1)。

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
  • 在数字 x 上左移 y 位得到 x * 2y：x << y === x * pow(2,y)。
// 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. 参考资料


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK