计算机中的数据都是以二进制的形式存储在设备中，虽然十进制比二进制所需要的存储空间少，但二进制在硬件实现上要简单很多，而且在数模转换上也更加容易，因为只需要两种状态，所以计算机的底层运算都采用二进制。位运算就是对二进制数据进行的运算。使用合理的位运算可以提高代码在机器上的执行效率，本文将介绍常见的位运算以及Python中的位运算。

位运算符

常见位操作符如下表：
| 运算符 | 含义 | Python示例 |
| :——: | :————: | :——————————————————: |
| & | AND 与 | x & y |
| | | OR 或 | x | y |
| ~ | NOT 非 | ~x |
| ^ | XOR 异或 | x ^ y |
| << | 左移 | x << 1(相当于x*2) |
| >> | 右移 | x >> 1(相当于x/2) |
| >>> | 无符号右移 | Python没有符号位，Java中可以使用此符号 |

上表列出的位运算符也可以进行复合赋值运算：
| 运算符 | Python示例 | 等价于 |
| :——: | :————: | :————: |
| & | x &= y | x = x & y |
| | | x |= y | x = x | y |
| ^ | x ^= y | x = x ^ y |
| << | x <<= 1 | x = x << 1 |
| >> | x >>= 1 | x = x >> 1 |
| >>> | x >>>= 1 | / |

注意与逻辑运算符的区别，逻辑与&&和逻辑或||具有短路求值特性，比如x && y运算，如果x为false，则不会计算y；x || y运算中，如果x为true，则不会运算y。

下面介绍这些位运算符的使用方法。

Python位运算

与 - &

按位与操作符就是按二进制位进行”与”运算，两位同时为1，结果为1，否则为0

>>> x = 6
>>> y = 12
>>> x & y
4
>>> bin(x)
'0b110'
>>> bin(y)
'0b1100'
>>> bin(x & y)
'0b100'

或 - |

或操作符进行按位或，只要其中一个为1，结果为1。

>>> x = 6
>>> y = 12
>>> x | y
14
>>> bin(x)
'0b110'
>>> bin(y)
'0b1100'
>>> bin(x | y)
'0b1110'

非 - ~

非操作符就是取反操作：~x = -(x+1)

1
2
3

>>> x = 6
>>> ~6
-7

异或 - ^

异或也就是相同为0，不同为1：

>>> x = 6
>>> y = 12
>>> x ^ y
10
>>> bin(x)
'0b110'
>>> bin(y)
'0b1100'
>>> bin(x ^ y)
'0b1010'

异或操作的一些特点：
1、x ^ 0 = x

1
2
3

>>> x = 6
>>> x ^ 0
6

2、x ^ (-1) = ~x

>>> x = 6
>>> x ^ -1
-7
>>> ~x
-7

3、x ^ (~x) = -1

1
2
3

>>> x = 6
>>> x ^ (~x)
-1

4、x ^ x = 0

1
2
3

>>> x = 6
>>> x ^ x
0

5、交换两个数

>>> x = 6
>>> y = 12
>>> z = x ^ y
>>> x ^ z
12
>>> y ^ z
6

6、结合律
x ^ y ^ z = x ^ (y ^ z) = (x ^ y) ^z

左移 - <<

按位左移操作符(<<)将其第一位向左移，在右边补零。对于左移操作相当于将数字乘以2的n次幂：x << n = x * 2^n。

>>> x = 6
>>> x << 1
12
>>> x << 2
24
>>> x << 3
48

注意在Python编程中，没有必要使用移位操作来提高执行效率，因为Python编译器已经优化了，使用移位操作反而降低了代码的可读性。

右移 - >>

按位右移操作符(>>)和左移相反，它是向右移动，左边补0。右移等价于：x >> n = floor(x / 2^n)

>>> x = 10
>>> x >> 1
5
>>> x >> 2
2
>>> x // 4
2

位运算其它应用

指定位置的位运算

将x 最右边的n 位清零：x& (~0 << n)
获取x 的第n 位值（0 或者1）：(x >> n) & 1
获取x 的第n 位的幂值：x& (1 <<n)
仅将第n 位置为1：x | (1 << n)
第n位取反：x ^ (1 << n)
仅将第n 位置为0：x & (~ (1 << n))
将x 最高位至第n 位（含）清零：x& ((1 << n) -1)

判断奇偶
x % 2 == 1 —> (x & 1) == 1
x % 2 == 0 —> (x & 1) == 0

>>> x = 10
>>> x & 1
0
>>> x= 11
>>> x & 1
1

将最低位的1清零

>>> x = 10
>>> bin(x)
'0b1010'
>>> x & (x - 1)
8
>>> bin(8)
'0b1000'
>>>

得到最低位的1

>>> x = 10
>>> bin(x)
'0b1010'
>>> x & -x
2

清0

1
2
3

>>> x = 10
>>> x & ~x
0

如果x和y是集合，Python中，位运算符可用于集合的运算，详见算法笔记：哈希表、映射和集合。

--THE END--
Python 位运算

本文标题:算法笔记：位运算

文章作者:hiyo

文章链接:https://hiyongz.github.io/posts/algorithm-notes-for-bitwise-operation/

许可协议:本博客文章除特别声明外，均采用CC BY-NC-ND 4.0 许可协议。转载请保留原文链接及作者。