Листать биты в питоне

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 экземплярами).

Answer 2

Для подсчета битов, когда вы замаскировали интересующий вас диапазон, см. Процедуру bitCount () на вики-странице python BitManipulation , которая реализует схему Брайана Кернигана:

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

Answer 3

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 4

Я не знаю python, поэтому я просто думаю об этом с точки зрения чистой математической агорифмии ...

Мне приходит в голову, что для первой части более эффективным методом может быть создание маски битов, которые вы хотите сначала переключить, как целое число. Чтобы упростить мне жизнь, я собираюсь предположить, что вы рассчитываете нижнюю и верхнюю границы от младшего значащего бита, равного 0, и самого старшего, равного 31 (или любого другого значения, подходящего для длины целого в вашем случае).

Если вы хотите, чтобы биты от n до m (m> n) были перевернуты, то в двоичном представлении числа 2 ^ (m + 1) -2 ^ n эти биты будут установлены. Затем сделайте XOR, и вы сделаете все обмены за один раз. Компьютер должен быть способен сделать это за один раз, а не по одному на бит.

Что касается подсчета, я не уверен. Есть способы подсчитать количество установленных бит в числе. Я не уверен, что вы получите повышение эффективности, используя вышеуказанную битовую маску с AND, чтобы обнулить все биты, которые вам не нужны для подсчета nad, затем использовать эти алгоритмы, или вам лучше изменить их, чтобы они работали на вас , Я не знаю, как они работают с моей головы. :)