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

然后,我还需要确定给定一个范围,比如从低到高,设置了多少位.我的代码如下:

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

对于"翻转",您可以制作单个位图(包含所有感兴趣位置的位图)和单个独占 - 或:

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

对于位计数,一旦隔离(n&mask)与上述RHS相同的"掩码",将其切换为例如8位片并在查找表中查找8位计数(只是简单list或者array.array为预先准备)是最快的方法.

gmpy有一些有用且快速的位操作和计数操作,尤其是 如果你处理非常长的字符串(超过机器字的价值,那么比Python的本机产品更快),因此在Python中它们就是long实例.