在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数,如果字符串是二进制的话,使用位运算异或可以非常简单的算出两字符串的汉明距离。

这里我们将介绍python3中如何使用二进制的使用以及二进制的位操作。

python里二进制的表示

Python中可以通过以”0b”或者”-0b”开头的字符串来表示二进制,当然我们也可以使用bin函数来对数值转换成二进制形式的字符串。

    print(0b1101)
    #13
    print(0b11111110)
    #254
    bin(5)
    #'0b101'

二进制的位操作

python里面提供的位操作

  • >> #右移
  • << #左移
  • | #位或
  • & #位与
  • ^ #位异或
  • ~ #非 下面具体来看

左移

《Python3二进制数值表示和位操作》

左移其实就是相当于把数字乘以2的左移位数次方。

0b11是3的机器码,移动后变成0b1100,变成12,3*2**2 == 12,同理上图其他的数字计算也可使用此法获得10进制的数值。

右移

    0b101001 >>2
    #10
    0b1011 >> 4
    #0
    0b1011 >> 3
    #1
    0b101101010 >> 3
    #45
    -16 >> 2
    #-4
    8 >> 1
    #4

右移便是除以2的N次方,这里N为右移的位数,当然这里是python2的计算结果,python3里面除得到的自动变为float数值,这是python3与python2的不同之处了。

    >>> 4/3
    1.3333333333333333
    >>> 4//3
    1

    >>> 0b1101 | 0b1010 
    15
    >>> 0b100 | 0b100 
    4

就是在二进制的位置上,只要对应的两个二进制任意一个为1,最终结果便是1,然后转变成10进制便是。

    >>> 0b110 & 0b100 
    4
    >>> 0b110 & 0b101 
    4

    >>> ~ 0b101 
    -6
    >>> ~ 0b100
    -5

非运算会处理符号位,所以数值会由正变负,由负变正。

异或

    >>> 0b111 ^ 0b101   
    2
    >>> 0b111 ^ 0b100   
    3

异或是只有两个数在同一位置出现不同数,一个为0,一个为1,结果才是1,否则为0.

这个特性可以用来比较差别的,比如要使0b111变成0b101需要变动几个字符,也就是bin(0b111 ^ 0b101 ).count(“1”)

python里面的位运算可以应用的地方往往很有意思,比如判断奇数还是偶数,可以用X%2 == 1也可以直接使用位运算X & 1