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

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

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

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. static void Main(string[] args)
2. {
3.   Console.Write("Podaj zakres [0, 2^k)\n k = ");
4.   int k = Convert.ToInt32(Console.ReadLine());
5.   int wynik = IleBitow(k);
6.   Console.WriteLine("Znalezionych bitów: {0}", wynik);
7.   Console.ReadKey();
8. }

• Kod źródłowy Implementacja