Đếm số lần mỗi bit được đặt trong một dãy số nguyên

Question

Cho một dải số nguyên từ M đến N, trong đó M và N có thể không phải là quyền hạn của 2. Có cách nào hiệu quả để đếm số lượng của lần mỗi bit được đặt?

Ví dụ phạm vi khoảng từ 0 đến 10

0 0000 
1 0001 
2 0010 
3 0011 
4 0100 
5 0101 
6 0110 
7 0111 
8 1000 
9 1001 
10 1010 

Tôi muốn đếm cho số lượng thời gian mỗi bit được thiết lập trong mỗi cột đó sẽ là 3,4,5,5 trong trường hợp này.

Answer 1

Mỗi cấp bit có mẫu bao gồm 2^power 0s theo sau là 2^power 1 giây.

Vì vậy, có ba trường hợp:

1. Khi M và N là như vậy mà M = 0 mod 2^(power+1) và N = 2^(power+1)-1 mod 2^(power+1). Trong trường hợp này câu trả lời đơn giản là (N-M+1)/2

2. Khi M và N là như vậy mà cả M và N = số lượng tương tự khi số nguyên chia 2^(power+1). Trong trường hợp này có một vài subcases:

   1. Cả M và N là như vậy mà cả hai M và N = số tương tự khi số nguyên chia 2^(power). Trong trường hợp này nếu N < 2^(power) mod 2^(power+1) thì câu trả lời là 0, khác câu trả lời là N-M+1
   2. khác họ là khác nhau, trong trường hợp này câu trả lời là N - (N/2^(power+1))*2^(power+1) + 2**(power) (phân chia số nguyên) nếu N > 2^(power) mod 2^(power+1), khác câu trả lời là (M/2^(power+1))*2^(power+1) - 1 - M

3. Trường hợp cuối cùng là nơi M và N = số khác nhau khi số nguyên chia cho 2^(power+1). Trường hợp này bạn có thể kết hợp các kỹ thuật của 1 và 2. Tìm số các số giữa M và (M/(2^(power+1)) + 1)*(2^(power+1)) - 1. Sau đó, giữa (M/(2^(power+1)) + 1)*(2^(power+1)) và (N/(2^(power+1)))*2^(power+1)-1. Và cuối cùng là giữa (N/(2^(power+1)))*2^(power+1) và N.

Nếu câu trả lời này có lỗi hợp lý trong đó, hãy cho tôi biết, nó phức tạp và tôi có thể đã làm rối tung điều gì đó một chút.

UPDATE:

thực hiện trăn

def case1(M, N): 
    return (N - M + 1) // 2 

def case2(M, N, power): 
    if (M > N): 
    return 0 
    if (M // 2**(power) == N // 2**(power)): 
    if (N % 2**(power+1) < 2**(power)): 
     return 0 
    else: 
     return N - M + 1 
    else: 
    if (N % 2**(power+1) >= 2**(power)): 
     return N - (getNextLower(N,power+1) + 2**(power)) + 1 
    else: 
     return getNextHigher(M, power+1) - M 


def case3(M, N, power): 
    return case2(M, getNextHigher(M, power+1) - 1, power) + case1(getNextHigher(M, power+1), getNextLower(N, power+1)-1) + case2(getNextLower(N, power+1), N, power) 

def getNextLower(M, power): 
    return (M // 2**(power))*2**(power) 

def getNextHigher(M, power): 
    return (M // 2**(power) + 1)*2**(power) 

def numSetBits(M, N, power): 
    if (M % 2**(power+1) == 0 and N % 2**(power+1) == 2**(power+1)-1): 
    return case1(M,N) 
    if (M // 2**(power+1) == N // 2**(power+1)): 
    return case2(M,N,power) 
    else: 
    return case3(M,N,power) 

if (__name__ == "__main__"): 
    print numSetBits(0,10,0) 
    print numSetBits(0,10,1) 
    print numSetBits(0,10,2) 
    print numSetBits(0,10,3) 
    print numSetBits(0,10,4) 
    print numSetBits(5,18,0) 
    print numSetBits(5,18,1) 
    print numSetBits(5,18,2) 
    print numSetBits(5,18,3) 
    print numSetBits(5,18,4) 

Answer 2

Nó có thể được giữ đơn giản như -

Tham x1 = 0001 (cho việc tìm kiếm 1 tại cột ngoài cùng bên phải), x2 = 0010, x3 = 0100 vv ..

Bây giờ, trong một vòng lặp đơn -

n1 = n2 = n3 = 0 
for i=m to n: 
    n1 = n1 + (i & x1) 
    n2 = n2 + (i & x2) 
    n3 = n3 + (i & x3) 

nơi - ni = số 1 trong cột i'th (từ phải sang)