深入理解按位操作符
按位操作符(Bitwise operators) 的计算主要用在二进制中,虽然平时很少有机会用到按位操作符,但不得不承认,在某些时候,这些操作符能够给我们提供很好的解决方案。
1. 概述
按位操作符(Bitwise operators) 的计算主要用在二进制中,虽然平时很少有机会用到按位操作符,但不得不承认,在某些时候,这些操作符能够给我们提供很好的解决方案。
下面介绍操作符时,也会提供一些比较经典的例子,来看看它们是如何巧妙地解决问题的吧。
2. 正文
2.1 二进制
本文假设你知道计算机中用二进制数来存储,计算数字,并且熟悉二进制数的表示方法。
讲解位操作符之前,先简单讲一下真值、原码、反码和补码。
2.1.1 真值
我们表示自然数包括正数,负数和 0,下面是 1 和-1 的二进制表示:
1 | + 00000001 # +1 |
2.1.2 原码
但是计算机只能存储 0 和 1,不能存储正负,所以一个数的最高位存放符号,正数为 0,负数为 1,用后面七位来表示真值的绝对值:
1 | 0 0000001 # +1 |
由于10000000
表示为 -0 ,这个没有意义,所以这个数字被用来表示 -128,所以负数就比整数多一个。
2.1.3 反码
反码的表示方法是:正数不变,负数是在其原码的基础上,符号位不变,其余位取反:
1 | 0 0000001 # +1 |
2.1.4 补码
补码的作用主要是为了简化运算,将减法变为加法而发明的数学表示法,其表示方法是:正数不变,负数是在其反码的基础上+1:
1 | 0 0000001 # +1 |
2.1.5 最后
1 | [+1] = [0000 0001]原 |
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
的运算过程:
1 | 11 = 0000 1011 |
注意:
- 任何数和 0 进行 AND 都为 0:
x & 0 = 0
。 - 任何数和 -1 进行 AND 都为自身:
x & -1 = x
。
例子 1(判断一个数的奇偶):
1 | // n & 1 === 0 |
例子 2(判断一个数是否为 2 的整数幂):
1 | // n & (n-1) === 0 |
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
的运算过程:
1 | 11 = 0000 1011 |
注意:
- 任何数和 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
的运算过程:
1 | 11 = 0000 1011 |
注意:
- 任何数和 0 进行 XOR 都为自身:
x ^ 0 = x
。 - 任何数和 -1 进行 OR 都为 ~x:
x | -1 = ~x
。
例子 1(不用临时变量交换两个数):
1 | var a = 10, |
例子 2(找到数组中出现奇数次的元素):
1 | // 一个非空数组,只有一个元素出现奇数次,其余出现偶数次,找出那个元素: |
2.2.4 NOT(非)
对每一个比特位执行非(NOT)操作。NOT a
结果为 a 的反转(即反码)。非操作的真值表:
a | NOT a |
---|---|
0 | 1 |
1 | 0 |
下面展示~11
的运算过程:
1 | 11 = [0000 1011]原 |
接着展示~-11
的运算过程:
1 | -11 = [1000 1011]原 |
注意:
- 对任何数 x 进行 NOT 操作的结果为 -(x + 1),
~x = -(x+1)
。
2.3 按位移动操作符
按位移动操作符有两个操作数:第一个是要被移动的数字,而第二个是要移动的长度。移动的方向根据操作符的不同而不同。
按位移动会先将操作数转换为高位字节顺序的 32 位整数,并返回与左操作符相同的类型。右操作数小于 32 位,否则只有最低 5 个字节会被使用。
2.3.1 <<(左移)
该操作数会将第一个操作数向左移动指定的位数。向左被移出的位被丢弃,右侧用 0 补充。
下面展示11<<2
的运算过程:
1 | 11 = [0000 1011]原 |
接着是-11<<2
的运算过程:
1 | 11 = [1000 1011]原 |
注意:
- 在数字 x 上左移 y 位得到 x * 2y:
x << y === x * pow(2,y)
。
例子:
1 | // 1.获得 int 型最大值 |
2.3.2 >>(有符号右移)
该操作符会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃,拷贝最左侧的位以填充左侧。由于新的最左侧的位总是和以前相同,符号位没有被改变。所以被称作“符号传播”。
下面展示11>>2
的运算过程:
1 | 11 = [0000 1011]原 |
接着是-11>>2
的运算过程:
1 | 11 = [1000 1011]原 |
例子:
1 | // 1.求两个整数的平均值(结果有小数点时抛弃小数点) |
2.3.3 >>>(无符号右移)
该操作符会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃,左侧用 0 填充。因为符号位变成了 0,所以结果总是非负的。(译注:即便右移 0 个比特,结果也是非负的。)
对于非负数,有符号右移和无符号右移总是返回相同的结果。例如:11 >> 2 === 11 >>> 2
。
而对于负数却不尽相同,下面展示-11>>>2
的运算过程(这里需要用到的位数较多,所以用 32 位整数演示):
1 | -11 = [1000 0000 0000 0000 0000 0000 0000 1011]原 |
🥳 加载 Disqus 评论