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. int IleBitow(int k) {
2.   int wynik = 0;
3.   for (int i = 0; i < (int)pow(2, k); i++) {
4.     int ile = 0;
5.     int tmp = i;
6.     while (tmp > 0) {
7.       ile += (tmp % 2);
8.       tmp >>= 1;
9.     }
10.     wynik += ile;
11.   }
12.   return wynik;
13. }

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. int IleBitow(int k) {
2.   int wynik = 0;
3.   for (int i = 0, tmp = 1; i < k; i++) {
4.     wynik = 2 * wynik + tmp;
5.     tmp *= 2;
6.   }
7.   return wynik;
8. }

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. int IleBitow(int k) {
2.   return pow(2, k - 1) * k;
3. }

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. int main () {
2.   int k;
3.   cout << "Podaj zakres [0, 2^k)\n k = ";
4.   cin >> k;
5.   int wynik = IleBitow(k);
6.   cout << "Znalezionych bitow: " << wynik;
7.   system("pause");
8.   return 0;
9. }

• Kod źródłowy Implementacja