位操作

2017-02-23 四 编程语言-Python Python

最近碰到一个问题，是取一个数的反数，所以整理了一下位操作。 计算机系统中所有的数据都是以二进制的形式存储的。位运算其实就是直接对在内存中的二进制数据进行操作，因此数据处理会比较快。 在实际编程中，如果能合理运用位操作，能提高运行效率，解决一些复杂问题。

位操作基础

基本的位操作符有与、或、异或、取反、左移、右移。运算规则如下：

注意：

1. 只有～为单目运算符，其他的为双目运算符
2. 位操作只能作用于整型数据
3. 位操作符的运算优先级比较低，因此使用时注意括号的添加
4. 位算符可以复合操作，比如&=、|=、^=、<<=、>>=。

常用位操作例子

1.判断奇偶

显然的，最末位为0的为偶数，为1的为奇数。因此可以使用a & 1是否为0来判断，如果为0则表明为偶数，为1表明为奇数

下面的程序，将输出0到100之间的所有偶数

1
2
3
4
5
6
7
8

#!/usr/bin/env python
# *-* utf-8 *-*

def geteven():
    for i in range(100):
        if i & 1 is 0:
            print i
geteven()

2.交换两数

一般的写法为，借助第三个变量来保存其中一个变量

def change(x,y):
    z=x
    x=y
    y=z
    return x,y

使用位操作，可以不借助第三个变量

首先 a^=b 即 a=(a^b) 然后 b^=a 即b = b^a 将a替换为(a^b)得到 b=b^(a^b),由于^满足交换率，b^(a^b)=b^b^a 由于一个数和自己异或的结果为0，并且任何书和0异或都不会变。因此 b=b^(a^b)=b^b^a=0^a。 b=a 最后a^=b即 a=a^b 前面已得到a=(a^b), b=a 所以 a=a^b即a=(a^b)^a = a^a^b=0^b=b 故代码还可以这样写

def change(x,y)
    x^=y
    y^=x
    x^=y
    return x,y

以具体的实例来说明一下：

比如x=7 y=5 7的二进制为 4+2+1 即0111 5的二进制为 4+1 即0101 第一步 x^=y x = 0111 ^ 0101 = 1101 第二步 y^=x y = 0101 ^ 1101 = 0111; 这时y为0111即7，也就是x 第三步 x^=y x = 1101 ^ 0111 = 0101; 这时x为0101即5，也就是y

3.交换符号

交换符号，顾名思义，即为正变负。 其实用普通方法也很简单： x=-x 例如 1 -1 -12 12 但通过位操作也很方便 比如 -11 11110101(-11) 取反为0001010 加1 为00001011 即11 00001011(11) 取反11110100 加1 为11110101 即-11 正负切换，只需原数取反后加1

代码如下：

def signchange(x):
    return ~x+1

4.求绝对值

位操作可以用来求绝对值，负数可以取反后加1.和前面讲的一样 如果32位有符号整型，右移31位得到最后一位符号位，如果为0，则为正数，如果为-1，为负数 正数直接返回，否则取反加1

代码如下：

 def getabs(x):
     sign = x >> 31
     if sign is 0:
         return x
     else:
         return ~x + 1

对于任何数，和0异或都会保存不变。与-1异或相当于取反。因此 x与sign异或后再减sign(sign要么为0，要么为-1，-sign要么减0或减-1等于+1）也可以得到绝对值，代码可以改为：

def getabs(x):
    sign = x >> 31
    return (x^sign) - sign

5.高低位交换

比如一个16位的无符号整数，前8位可以作为“高位”，后8位可以为“低位”，将其高低互换。 如34520: 10000110 11011000 变为 11011000 10000110 55430 将10000110 11011000 右移8位，即得到00000000 10000110，左移8位得到，11011000 00000000，然后将两个数相或得到11011000 10000110 代码如下：

def changesite(x):
    return (x >> 8) | (x << 8)

此处 python可能得到值不同，python默认为有符号数，且为64位

6.二进制逆序

逆序就是将34520 10000110 11011000变为 00011011 01100001

类似于归并排序的分组处理，可以通过4步进行16位数据的二进制逆序： 第1步：2位一组，每位高低交换： 10000110 11011000 01001001 11100100 第2步：4位一组，每2位高低交换 01001001 11100100 00010110 10110001 第3步：8位一组，每4位高低交换 00010110 10110001 01100001 00011011 第4步，16位一组，8位高低交换 01100001 00011011 00011011 01100001 这样就得到了二进制交换的目的

第一步如何进行交换？

先分别取其奇数位和偶数位，空位以0补位 奇数位：10000010 10001000 偶数为：00000100 01010000 然后将奇数位右移1位得到 01000001 01000100 偶数位左移1位得到 00001000 10100000 两则相或得到： 01001001 11100100 这样就得到了奇偶位的数据交换

代码如下：

def getnum(x):
    x = ((x&0XAAAA) >> 1) | ((x&0X5555) <<1);
    x = ((x&0XCCCC) >> 2) | ((x&0X3333) <<2);
    x = ((x&0XF0F0) >> 4) | ((x&0X0F0F) <<4);
    x = ((x&0XFF00) >> 8) | ((x&0X00FF) <<8);
    return x

7.二进制按位取反

例如 5=101 变为010 2 1=1 变为0 7=111 变为000 变化可以简单归结为1变0 0变1 异或的特点是相同为0，不同为1；如果和1相异或，1就会变成0，0就会变成1，也就是将原数的每位和1相异或就能得到对应的取反 比如 101: 101 ^ 111 得到 010 111： 111^111得到000 现在问题转为如何获取和原数相同的全数为1的数 获取原数的位数，如111可由1000 - 1 获取 方法1 1左移获得，1移位后右边补0 代码如下：

def getnum(num):
    i = 1
    while i <= num:
        i = i << 1
        print(i)
    return (i - 1) ^ num

2.获取原数的位数，求相同位数的最大数 代码如下：

def getnum(num):
    n = int(math.log(num,2)) + 1
    m = 2**n
    return (m-1) ^ num

8 二进制中１的个数

统计二进制数中１的个数，这个方法比较多，可由转成字符进行统计。这里采用位操作的方法。 下面还是以34520为例，进行分析 １.２位一组高低位相加 　10 00 01 10 11 01 10 00 ->01 00 01 01 10 01 01 00 2.4位一组高低位相加 01 00 01 01 10 01 01 00 00 01 00 10 00 11 00 01 3.8位一组高低位相加 00 01 00 10 00 11 00 01 00 00 00 11 00 00 01 00 4.16位一组高低位相加 　00 00 00 11 00 00 01 00 　00 00 00 00 00 00 01 11 　 这方法的套路在于二进制无非０和１，第一步相当于分别把８组里面的１进行了统计，第二步又把４组里面的１进行了统计，然后2组，然后1组 代码：

def getsum(x):
     x = ((x & 0xaaaa) >> 1) + (x & 0x5555)
     x = ((x & 0xcccc) >> 2) + (x & 0x3333)
     x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f)
     x = ((x & 0xff00) >> 8) + (x & 0x00ff)
     return x

分组处理可以解决很多二进制问题。

9.落单的数字

一组数字，大部分都是出现了偶数次，而缺失的数字出现了奇数次，现在要找出这个数。 利用异或运算的两个特性，１．自己和自己异或为０（和０异或为本身）　２．异或满足交换率 也就是将所有的数进行异或，成对的数就会变成０，最后就变成了一堆０和落单的数异或，也就找到了它

代码如下：

def getnum(numlist):
    num=0
    for i in numlist:
        num ^= i
    return num

例如getnum([7,6,4,3,3,4,6,3,3,7,7]) 将输出7

要是两个落单了呢 比如[2,3,4,5,6,7,8,9,9,8,7,5,3,2] 如果按照上面的做法，最终得到的是两个落单数字的异或结果。 如果将整组数分成两组，并且将两个落单的数分别分到两组中，两组分别异或就能把两个落单的数孤立出来。 如何分组呢，相同的数在每个二进制上的位都相同，两个相同的数异或后，每位上都是０，而不同的数异或后至少有一位为１,我们就按这一位为０的分为１组，为１的分为１组 例子中异或结果为6^4 0110^0100 为0010 也就是７和４在第１位不同，然后将整个数组按照第１位　１和０进行分组 ２　0010　第一组 ３　0011 第一组 ４　0100 第二组 ５　0101 第二组 ６　0110 第一组 ７　0111 第一组 ８　1000 第二组 ９　1001 第二组 这样 ２、３、６、７、７、３、２为１组　 4、５、８、９、９、５为２组 这样每组分别异或就得到了6和４

代码：

def getdouble(numlist):
    num = 0
    for i in numlist:
        num ^= i
    n = int(math.log(num,2)) + 1
    for j in range(n):
        if((num >> j)&1 ==1):
            break
    list1=[]
    list2=[]
    for temp in numlist:
        if ((temp >> j)&1 ==1):
            list1.append(temp)
        else:
            list2.append(temp)
    print getsingle(list1)
    print getsingle(list2)