每個位在整數範圍內設置的次數

Question

給定從M到N的整數範圍，其中 M和N可能不是2的乘方。是否有 有效的方法來計算每次 位設置了多少次？

例如範圍爲0〜10

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

我想的時間每個比特中這將是3,4,5,5在這種情況下的每一列設置的數目的計數。

Answer 1

每個比特級別具有由2^power 0s組成的模式，然後是2^power 1s。

因此，有三種情況：

1. 當M和N是這樣的：M = 0 mod 2^(power+1)和N = 2^(power+1)-1 mod 2^(power+1)。在此情況下，答案是簡單地(N-M+1)/2

2. M時和N使得M和N =相同數目的整數時通過2^(power+1)劃分。在這種情況下有幾個子情況：

   1. 兩者M和N是，使得兩個M和N =當通過整數分割2^(power)相同數目。在這種情況下，如果N < 2^(power) mod 2^(power+1)那麼答案是0，否則答案是N-M+1
   2. 否則它們是不同的，在這種情況下，答案是N - (N/2^(power+1))*2^(power+1) + 2**(power)（整數除法）如果N > 2^(power) mod 2^(power+1)，否則答案是(M/2^(power+1))*2^(power+1) - 1 - M

3. 最後一種情況是當整數除以2^(power+1)時，M和N =不同的數字。這種情況下，您可以結合使用1和2的技術。查找M和(M/(2^(power+1)) + 1)*(2^(power+1)) - 1之間的數字數。然後在(M/(2^(power+1)) + 1)*(2^(power+1))和(N/(2^(power+1)))*2^(power+1)-1之間。最後在(N/(2^(power+1)))*2^(power+1)和N之間。

如果這個答案有邏輯錯誤，讓我知道，這很複雜，我可能已經有些微不足道。

UPDATE：

Python實現

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

它可以保持一樣簡單 -

取X1 = 0001（用於找到1份的在最右邊的列），X2 = 0010，X3 = 0100等等。

現在，在一個循環 -

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

哪裏 - NI = 1只在第i個列（右）