在Python中翻转位

Question

给定一个整数 n，我想要在这个数字的二进制表示中，把某个范围内的所有位进行切换，比如从下限到上限。为此，我做了以下操作 [bit_string 是一个包含 1 和 0 的字符串，表示 n 的二进制形式]

for i in range(lower,upper+1):
   n ^= (1 << len(bit_string)-1-i) #Toggle the ith bit

然后，我还需要确定在给定的范围内，比如从下限到上限，有多少个位是被设置为 1 的。我的代码是这样的：

number_of_ones = 0
for i in range(lower,upper+1):
    if(n & (1 << len(bit_string)-1-i)): #Check the ith bit
      number_of_ones+=1

不过，如果 n 的值非常大，我觉得这些算法会比较慢。有没有办法让这两个操作更快或者更高效呢？

谢谢

Answer 1

在计算位数时，一旦你把感兴趣的范围遮罩掉，可以查看一下 python位操作维基页面 上的 bitCount() 函数，它实现了布莱恩·肯尼汉的方法：

def bitCount(int_type):
    count = 0
    while(int_type):
        int_type &= int_type - 1
        count += 1
    return(count)

Answer 2

def bitflip(n,range):
    bitfliplen = range[1]-range[0]
    return n ^ ((2**bitfliplen-1) << (range[0]))

运行中：

>>> a = 47727124L
>>> b = bitflip(a,(5,10))
>>> print "a: {0:b}\nb: {1:b}".format(a,b)
a: 10110110000100001000010100
b: 10110110000100000111110100
>>>

Answer 3

关于“翻转”，你可以创建一个单一的位图（在所有感兴趣的位置上填充1），然后进行一次异或操作：

n ^= ((1<<upper)-1)&~((1<<lower)-1)

对于位计数，一旦你用相同的“掩码”隔离出(n & mask)，可以把它切成比如8位的小块，然后在一个查找表中查找这些8位的计数（这个查找表可以事先准备好，简单来说就是一个list或array.array）。这种方法是比较快的。

gmpy提供了一些有用且快速的位操作和计数功能，特别是当你处理非常长的位串时（超过一个机器字的长度，在Python中这些会是long类型），它的速度比Python自带的要快。