Python二进制表示和位操作

我们都知道在计算机中所有的信息最终都是以二进制的0和1来表示，而有些算法是通过操作bit位来进行运算的，这就需要我们了解Python中如何去表示二进制，又如何是进行位运算的。

二进制的表示

首先在Python中可以通过以"0b"或者"-0b"开头的字符串来表示二进制，如下所示 

1
2
3
4
print 0b101 # 输出5
print 0b10  # 输出2
print 0b111 # 输出7
print -0b101 # 输出-5

由此可知我们用二进制表示的数字在打印之后会变成我们更为熟悉的十进制数，更容易被人理解。 当我们需要看十进制数字的二进制表示时，可以使用bin函数 

1
bin(5)  # 输出0b101

二进制的位操作

首先一点需要明确的是所有的运算（包括位操作）在计算机内部都是通过补码形式来进行运算的，关于补码可以参考文章原码，反码和补码，计算机内部运算示意图如下： image

在Python中提供了如下二进制的位操作： 

1
2
3
4
5
6
>>  #右移
<<  #左移
|   #位或 
&   #位与
^   #位异或
~   #非

位运算法则：

image

下面我们分别来看下：

左移

1
2
3
4
0b11 << 2   #输出为12, 即0b1100
5 << 2      #输出为20, 即0b10100
-2 << 2     #输出为-8
5 << 64     #输出为92233720368547758080L

  1. 以0b11为例，0b11的补码就是0b11，所以左移就是将所有的0和1的位置进行左移，移位之后将空位补0。
  2. 负数的左移相对来说就比较复杂，以-2 << 2为例，-2的原码是10000000000000000000000000000010（32位系统），其补码为11111111111111111111111111111110，左移之后变为11111111111111111111111111111000，再转化为原码即10000000000000000000000000001000，也就是-8，也就是-2*(2**2)=-8
  3. 左移超过32位或者64位（根据系统的不同）自动转化为long类型。
  4. 左移操作相当于乘以2**n，以5 << 3为例，相当于5*(2**3),结果为40。
右移

1
2
3
0b11 >> 1   #输出为1, 即0b1
5 >> 1      #输出为2，即0b10
-8 >> 3     #输出为-1

  1. 在Python中如果符号位为0，则右移后高位补0，如果符号位为1，则高位补1；
  2. 同样需要先转化为补码再进行计算，以-8 >> 3为例，-8的原码为10...01000,相应的补码为11...11000,右移后变为1...1,相应的原码为10...01,即-1。
  3. 右移操作相当于除以2**n，8 >> 3相当于8/(2**3)=1
或

1
2
0b110 | 0b101   #输出7,即0b111
-0b001 | 0b101  #输出-1

同样是转化为补码后再进行或运算, 只要有一位有1就为1。 所以或运算常常用于mask技术中的打开开关，即针对某一位把其置为1 比如将某个数字的第三位置为1，我们可以将mask设置为0b100，然后再或运算 

1
2
mask = 0b100
0b110000 | mask  #turn on bit 3

与

1
0b110 & 0b011   #输出2，即0b010

与运算常常用于mask技术的关闭开关，即针对某一位把其置为0 

1
2
mask = 0b10
0b111111 & mask  #turn off bit 2

异或

1
2
0b111 ^ 0b111   #输出0
0b100 ^ 0b111   #输出3

异或常用于将所有的位反转 

1
0b1010 ^ 0b1111  #输出5，即0b0101

非

1
2
~0b101  #输出2，即0b010
~-3     #输出2

非运算就是把0变1，1变0，唯一需要注意的是取非时符号位也会变换，比如-3，原码是10...011,补码是11...101,取非后变为00...010,由于符号位为0，所以对应的原码即为其本身，即2。

二进制工具

bitarray

关于bit有一个很有用的Packag叫做bitarray，其中bitarray对象可以帮助我们存储0，1值或者Boolean值，并像list一样进行操作。 

1
2
3
4
5
6
7
8
9
10
11
12
from bitarray import bitarray

#初始化一个有10个bit位的数组，初始值为0
a = bitarray(10)

#可以像操作list一样操作bitarray对象
a[1:8] = 1

#bitarray还提供了一些特殊的方法，如：all()
#当bitarray中所有的元素都为1时，all()返回为True
if a.all():
    print "all bits are True."

关于bitarrary的说明详见Github上的bitarray项目

位运算的应用

常见的应用如判断奇偶数 X & 0x1，变换符号位 ~X + 1，数字交换等，详细可以看参考链接中的文章 下面笔者想就实际项目中的一个例子来说明位操作的应用。

下表是一个TS Package header的说明（TS流是流媒体行业常用的传输格式），我们看到为了减少不必要的浪费，包头在定义域的时候都是按位进行定义的，那么我们如果想要取相应的域的值，也就需要使用位操作了。

Packet Header（包头）信息说明

序号 名称 bit数 说明
1 sync_byte 8bits 同步字节
2 transport_error_indicator 1bit 错误指示信息（1：该包至少有1bits传输错误）
3 payload_unit_start_indicator 1bit 负载单元开始标志（packet不满188字节时需填充）
4 transport_priority 1bit 传输优先级标志（1：优先级高）
5 PID 13bits Packet ID号码，唯一的号码对应不同的包
6 transport_scrambling_control 2bits 加密标志（00：未加密；其他表示已加密）
7 adaptation_field_control 2bits 附加区域控制
8 continuity_counter 4bits 包递增计数器

我们以取PID值为例，当我们获取到包头的字节串之后，我们需要如下几个步骤：

  1. 需要取到第2个字节，然后忽略第二个字节的高三位（从表中可以看出高三位为其它信息与PID无关）；
  2. 将第二个字节的后5位数字左移8位，这样将其移到高位；
  3. 移位后与第3个字节的数值相加得到PID的值。

要实现第一步，首先就要用到位操作中常用的mask技术，即通过将对应位为0的数值进行&操作 

1
0b10110111 & 0b00011111 #将高位的3位进行mask关闭操作，使得其值被去除

要实现第二步，就需要用到左移操作，左移操作之后与第三个字节的数值相加就是实际的PID值 完整代码实现如下： 

1
2
3
4
def get_package_pid(package):
    if package is None:
        raise Exception("get_package_pid param package is None.")
    return ((ord(package[1]) & 0x1f) << 8) + ord(package[2])

注:

1, ord()将byte串转化为对应的数字从而进行位运算；

2, 0x1f是十六进制表示，转化为二进制就是0b00011111.

参考链接：

https://segmentfault.com/a/1190000003789802

https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html

https://github.com/wnduan/codecademy-py/blob/master/Bitwise-Operators.md

http://developer.51cto.com/art/200808/83641_all.htm