Her bitin bir tam sayı aralığında ayarlanma sayısını sayma

Question

M ila N arasında bir tamsayı aralığı verildiğinde, M ve N 2'nin gücü olmayabilir. etkinliğini saymanın bir yolu var. her bir bit sayısı ayarlandı mı? Örneğin

aralığı 0 ile 10

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

I her bit bu durumda 3,4,5,5 olurdu her sütun yer almaktadır zamanın sayısı için sayımları istiyorum.

Answer 1

Her bit düzeyi, 2^power 0s ve ardından 2^power 1s'den oluşan bir desene sahiptir.

Yani üç durum vardır: M ve N öyle ki M = 0 mod 2^(power+1) ve N = 2^(power+1)-1 mod 2^(power+1) olan

1. . Bu durumda, bir cevap M ve N M ve N = aynı sayıda iki tamsayı 2^(power+1) bölündüğü zaman böyle olduğunda, sadece (N-M+1)/2

2. olup.

   1. Hem M ve N böyle hem M ve N = tamsayı 2^(power) bölünmesiyle aynı sayıda olun: Bu durumda birkaç subcases vardır. Bu durumda N < 2^(power) mod 2^(power+1) sonra cevap (tamsayı bölme) N > 2^(power) mod 2^(power+1) eğer başka cevap (M/2^(power+1))*2^(power+1) - 1 - M

3. olduğu başka cevap Başka onlar farklıdır

4. N-M+1, bu durumda cevap N - (N/2^(power+1))*2^(power+1) + 2**(power) olduğu, 0 ise Son durum, tamsayı 2^(power+1)'a bölündüğünde, M ve N = farklı sayılardır. Bu durumda 1 ve 2 tekniklerini birleştirebilirsiniz. M ve (M/(2^(power+1)) + 1)*(2^(power+1)) - 1 arasındaki sayıların sayısını bulun. Sonra (M/(2^(power+1)) + 1)*(2^(power+1)) ve (N/(2^(power+1)))*2^(power+1)-1 arasında. Ve son olarak (N/(2^(power+1)))*2^(power+1) ve N arasında.

Bu yanıtın içinde mantıksal hatalar varsa, bana bildirin, karmaşıktır ve bir şeyleri biraz karıştırmış olabilirim.

GÜNCELLEME:

piton uygulaması

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

Bu kadar basit tutulabilir -

alın x1 = 0001, x2 (en sağdaki sütunda 1'ler bulmak için) = 0010, x3 = 0100 ve benzeri ..

Şimdi, tek bir döngü içinde -

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

nerede - ni = (sağdan) i'inci sütunundaki 1'ler