Lật bit trong python

Question

Cho một số nguyên n, tôi muốn chuyển đổi tất cả các bit trong biểu diễn nhị phân của số đó trong phạm vi nói từ trên xuống dưới. Để làm điều này tôi thực hiện như sau [bit_string là một chuỗi chứa 1 và 0 và là một biểu diễn nhị phân của n]

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

Sau đó, tôi cũng cần phải xác định đó được đưa ra một phạm vi, nói thấp hơn để phía trên, làm thế nào nhiều bit được đặt.Mã để thực hiện điều đó như sau:

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 

Nhưng, nếu n rất lớn, tôi nghĩ các thuật toán này sẽ chậm. Có cách nào để làm cho hai hoạt động này nhanh hơn/hiệu quả hơn không?

cảm ơn

Answer 1

Đối với "lật", bạn có thể làm cho một bitmap đơn (với những người thân ở mọi tư thế của lãi) và một đơn độc-hay:

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

Đối bit đếm, một khi bạn cô lập (n & mặt nạ) cho cùng một "mặt nạ" như trên RHS, cắt nó thành ví dụ 8-bit lát và tìm kiếm số 8-bit trong một bảng tra cứu (chỉ cần một đơn giản list hoặc array.array để chuẩn bị trước) là về cách tiếp cận nhanh nhất.

gmpy có một số thao tác thao tác và đếm bit hữu ích và nhanh chóng, đặc biệt. nhanh hơn các dịch vụ gốc của Python nếu bạn đang xử lý các chuỗi bit rất dài (nhiều hơn giá trị của một từ máy, vì vậy trong Python chúng sẽ là long trường hợp).

Answer 2

Tôi không biết python vì vậy tôi chỉ nghĩ này từ một điểm mathsy agorithmy tinh khiết của xem ...

Nó xảy ra với tôi rằng cho phần đầu tiên một phương pháp hiệu quả hơn có thể là để xây dựng một mặt nạ của các bit bạn muốn chuyển đổi đầu tiên dưới dạng số nguyên. Để làm cho cuộc sống dễ dàng cho tôi tôi sẽ giả định rằng bạn đang đếm giới hạn dưới và trên của bạn từ bit ít nhất là 0 và đáng kể nhất là 31 (hoặc bất cứ điều gì là thích hợp cho chiều dài của một int trong trường hợp của bạn).

Nếu bạn muốn bit n đến m (m> n) được lật thì biểu diễn nhị phân của số 2^(m + 1) -2^n sẽ có các bit được đặt. Sau đó, làm một XOR và bạn làm tất cả các hoán đổi trong một đi. Máy tính nên được abel để làm điều này trong một đi có lẽ thay vì một cho mỗi trao đổi bit.

Đối với việc đếm, tôi không chắc chắn. Có nhiều cách để đếm số bit thiết lập trong một số. Tôi không chắc liệu bạn có đạt được hiệu quả khi sử dụng bitmask ở trên với AND và 0 trong tất cả các bit mà bạn không quan tâm về việc đếm nad hay không, sau đó sử dụng các thuật toán đó hoặc nếu bạn tốt nhất thay đổi chúng để làm việc cho bạn . Tôi không biết làm thế nào họ làm việc ra khỏi đỉnh đầu của tôi mặc dù. :)

Answer 3

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

Chạy:

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

Answer 4

Đối đếm bit, một khi bạn đã đeo mặt nạ ra phạm vi mà bạn quan tâm, vui lòng xem thói quen bitCount() trên python BitManipulation wiki page mà thực hiện âm mưu của Brian Kernighan:

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