Policz Bity

Zadanie

Dany jest pewien zakres liczb od 0 do 2^k. Oblicz sumę licznika bitów 1 dla każdej liczby z zakresu. Czy istnieje jakaś reguła, którą można to opisać? Jeśli tak to napisz algorytm, który ją wykorzysta.

Przykład

Przykładowo dla zakresu [0, 8) mamy następujące zapisy binarne:

1. dec / bin
2. 0 = 000
3. 1 = 001
4. 2 = 010
5. 3 = 011
6. 4 = 100
7. 5 = 101
8. 6 = 110
9. 7 = 111

Wynik to suma liczby bitów w każdym rozwinięciu binarnym czyli 0 + 1 + 1 + 2 + 1 + 2 + 2 + 3 = 12.

Implementacja

Rozwiązanie Proste

Najprostsze rozwiązanie polega na zastosowaniu pętli, która dla każdej kolejnej wartości z zakresu wyliczy ile jest w niej bitów 1, a następnie zsumuje wyliczane wartości. Oto przykładowo metoda IleBitow():

1. def IleBitow(k):
2.   wynik = 0
3.   for i in range(pow(2, k)):
4.     ile = 0
5.     tmp = i
6.     while (tmp > 0):
7.       ile += (tmp % 2)
8.       tmp >>= 1
9.     wynik += ile
10.   return wynik

Złożoność takiego rozwiązania wynosi O(2^{k + 1}), ponieważ dominującą operacją jest tutaj zliczanie bitów 1, a to wykonujemy maksymalnie 2^k razy dla 2^k liczb.

Optymalizowanie

Istnieje jednak pewna zależność pomiędzy kolejnymi etapami liczenia. Warto zauważyć, że jeśli zostało wygenerowane 2^k - 1 liczb to wystarczy je ponownie przepisać i dołączyć na początku wartość 1. Przykładowo mając liczby {0, 1} tablicę rozszerzamy przepisując jej aktualne elementy, a potem pownie z modyfikacją czyli {0, 1, 10, 11}. Na podstawie tego można stwierdzić, że a_k = 2a_{k - 1} + 2^{k - 1}. Wyrazem początkowym a₀ = 0

Na podstawie podanego wzoru można napisać funkcję, która będzie udzielać odpowiedzi w czasie liniowym:

1. def IleBitow(k):
2.   wynik = 0
3.   tmp = 1
4.   for i in range(k):
5.     wynik = 2 * wynik + tmp
6.     tmp *= 2
7.   return wynik

Tym razem złożoność zmalała do O(k), ponieważ wykorzystujemy poprzednie wyniki, aby szybciej obliczyć kolejne. Oczywiście wadą takiej metody jest to, że nie działa dla dowolnego zakresu jak poprzednie rozwiązanie, ale w tym przypadku takie uproszczenie jest akceptowalne.

Wzór

Jednak czy można uzyskać czas O(1)? Oczywiście, ale trzeba zamienić wzór rekurencyjny na wzór na n-ty wyraz ciągu. Istnieje do tego wiele metod, które na końcu zwrócą wzór a_k = 2^{k - 1}k. Można to wyjaśnić w następujący sposób:

a_k = 2a_{k - 1} + 2^{k - 1}
a_k = 2(2a_{k - 2} + 2^{k - 1}) + 2^{k - 1} = 4a_{k - 2} + 2^{k - 1} + 2^{k - 1}
a_k = 8a_{k - 2} + 2^{k - 1} + 2^{k - 1} + 2^{k - 1}
...
a_k = 2^{k - 1} + ... + 2^{k - 1} + 2^{k - 1} + 2^{k - 1} = 2^{k - 1}k

Jak można zauważyć przy każdym podłożeniu a_{k - j} zostaje dodatkowa wartość 2^{k - 1}, a pierwszy czynnik jest coraz większy. Jednak dla k-tego wyrazu a_{k - j} = a_{k - k} = a₀ 0, więc pierwszy, rekurenycjny czynnik zniknie i pozostanie k wartości 2^{k - 1}.

1. def IleBitow(k):
2.   return int(pow(2, k - 1)) * k

Zastosowanie wzoru upraszcza wzór do absolutnego minimum i osiągamy w ten sposób najlepszą możliwą złożoność.

Testowanie funkcji

Test funkcji można wykonać przy pomocy poniższej funkcji, która dla podanej wartości k zwróci liczbę bitów ustawiony na wartość 1.

1. k = int(input("Podaj zakres [0, 2^k)\n k = "))
2. wynik = IleBitow(k)
3. print("Znalezionych bitów:", wynik)

• Kod źródłowy Implementacja