各ビットが整数の範囲で設定された回数の回数

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のパターンを持ちます。

だから3例があります：MとNは、そのM = 0 mod 2^(power+1)やN = 2^(power+1)-1 mod 2^(power+1)です

1. 。この場合、答えはMとNは、MとN =整数2^(power+1)で割った同じ数の両方ようなものである場合には、単に(N-M+1)/2

2. あります。

   1. 両方MとNは、共にMとN = 2^(power)整数で割っ同数その：この場合、いくつかのサブケースがあります。この場合、N < 2^(power) mod 2^(power+1)はその後、答えは答えは、それらが異なるN-M+1エルス
   2. ある答えは(M/2^(power+1))*2^(power+1) - 1 - M

3. ある他N > 2^(power) mod 2^(power+1)、この場合には答えはN - (N/2^(power+1))*2^(power+1) + 2**(power)（整数除算）である他、0ある場合最後のケースは、整数を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

それはのようにシンプルに保つことができる - 、×2 = 0010、X3（右端の列で1つのを見つけるための）

テイク×1 = 0001 = 0100など..シングルループで今

、 -

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

場所 - NI =（右から）i番目の列内の1つの数