在Python中翻转比特

Question

给定一个整数n，我想翻转该数字在二进制表示中范围为lower到upper的所有位。 为此，我执行以下操作[bit_string是一个包含1和0的字符串，表示n的二进制表示形式]

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

然后，我还需要确定在给定范围内（例如从下限到上限），有多少位被设置。我的代码如下：

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非常大，我认为这些算法会变得很慢。有没有一种方法可以使这两个操作更快/更有效？

谢谢

- Tom

---

你正在进行位翻转，但是在Python中是针对字符串的...在更大的上下文中，这样做有什么作用？如果你关心速度，我认为你的方法完全错误。 - Nick T

这是我正在处理的一个编程问题 :) ... 我应该使用其他语言，比如C或C++吗？ - Tom

对于第二部分，您可以使用相同的位掩码进行“与”操作，然后使用以下链接中的算法：https://dev59.com/23VD5IYBdhLWcg3wDG_m（汉明重量）。 - Mark Peters

@Mark Peters：只有当它不是“long”（也就是说，其值超过2 ** 31-1）时才正确吧？ - Nick T

Answer 1

对于“翻转”，您可以制作一个单一的位图（在所有感兴趣的位置上都是1），然后进行单个异或操作：

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

如果要对位数进行计数，一旦你将(n & mask)与上面的RHS使用相同的"mask"隔离开来，将其切成例如8位片段，并在查找表中查找8位计数（事先只需准备一个简单的list或array.array），这是最快的方法之一。

gmpy具有一些有用且快速的位操作和计数操作，特别是当处理非常长的位串时（超过机器字长，因此在Python中它们将是long实例）比Python本地提供的更快。

- Alex Martelli

---

该死，又被打败了。除了没有任何有用的代码外，我只回答了一半的问题。 :) 不过我喜欢查找表的想法。我总是忘记它们可以提高速度。 :) - Chris

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
>>>

- Nick T

Answer 3

对于位计数，一旦你屏蔽了你感兴趣的范围，可以查看Python 位操作维基页面上实现Brian Kernighan方案的bitCount()例程：

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

- Von

Answer 4

我不懂Python，所以我只是从纯数学算法的角度考虑这个问题...

我想到了一个更有效的方法来构建你想要切换的位的掩码作为整数。为了方便起见，我假设您从最低位为0，最高位为31（或适用于您的int长度的任何值）开始计算您的下限和上限。

如果您想要翻转n到m（m>n）位，则数字2^(m+1)-2^n的二进制表示将设置这些位。然后进行异或操作，您可以一次完成所有交换。计算机应该能够一次性完成这些操作，而不是每个位交换一次。

至于计数，我不确定。有一些方法可以计算一个数字中设置的位数。我不确定是否使用上述位掩码与AND一起将您不关心计数的所有位清零，然后使用这些算法会提高效率，还是最好修改它们以适应您的需求。我不知道它们如何工作，但我相信它们可以帮助您解决问题。 :)

- Chris