Zadanie rekrutacyjne #1


To jest pierwszy wpis z cyklu “Zadanie rekrutacyjne”. Zamierzam publikować przykłady zadań wraz z rozwiązaniami. Celem jest pokazanie procesu ewolucji rozwiązania od najprostszego do ostatecznego.

Zadanie – policz jedynki w zapisie binarnym liczby

Zaimplementuj funkcję, która zwraca ilość ustawionych bitów w argumencie.

Przykładowe wyniki

ArgumentWynik
00
11
21
32
2558
32542313

 

Rozwiązanie z tablicą bitów

Najprostsze naiwne rozwiązanie. Tworzymy obiekt typu std::bitset i inicjujemy go argumentem funkcji. Następnie iterując po wszystkich bitach, obliczamy ich sumę, co jest tożsame z policzeniem jedynek.

Wady powyższego rozwiązania

  • konstruujemy złożony obiekt tylko po to, aby dokonać konwersji na postać bitową,
  • ilość operacji nie zależy od pozycji najbardziej znaczącego bitu.

Rozwiązanie z dzieleniem

Dzielimy z resztą, aby uzyskać wartości poszczególnych bitów.

Wady powyższego rozwiązania

  • wykonujemy wielokrotnie bardzo kosztowną operacje dzielenia,
  • zmienna w pamięci jest reprezentowana binarnie, mimo to traktujemy ją jak wartość dzietną.

Rozwiązanie z przesuwaniem bitów

Pozbyliśmy się dzielenia na rzecz znacznie prostszego przesuwania bitów i operacji AND.

Wady powyższego rozwiązania

  • wykonujemy wielokrotnie nieco prostsze operacje bitowe,
  • ilość operacji nie zależy od pozycji najbardziej znaczącego bitu.

 

Rozwiązanie z tablicą wartości dla każdego bajtu

Teraz dzielimy nasz argument funkcji na jednobajtowe bloki. Dla takiego bloku o rozmiarze 8 bitów przeliczyliśmy wcześniej ilość ustawionych bitów i stabilizowaliśmy te wartości. Taki zabieg dał nam ośmiokrotne zmniejszenie ilość operacji bitowych, natomiast musimy teraz stabilizować 256 wcześniej przeliczonych wartości. Po przetworzeniu bloku sprawdzamy, czy pozostała wartość ma chociażby jeden bit ustawiony, jeśli nie – to przerywamy.

Dalsza lektura

Bit Twiddling Hacks

6 thoughts on “Zadanie rekrutacyjne #1

  1. A dlaczego nie widzę rozwiązania używającego __builtin_popcount. Funkcja maszynowo zlicza bity – jest szybka 🙂
    Kod:
    uint PoliczBity(T n)
    {
    uint res = 0;
    for (unsigned long* ptr = (void*)(&n); ptr < &n + sizeof(n); ptr++)
    res+=__builtin_popcountl (*ptr)
    return res;
    }

    Pętla wykona sizeof(T)/sizeof(unsigned long) iteracji i będzie to nieco szybsze niż skakanie po pamięci i nie wymaga preprocessingu.

    1. Cieszę się ze podajecie swoje rozwiązania. Nie było moją intencją omówienie wszystkich możliwości. W Linkach znajduje się odnośnik do szerszego artykułu.

  2. Można też w pętli wyciągąć najmniejszy zapalony bit przez arg & (-arg) dopóki zmienna nie jest zerem.

  3. Bardzo fajny sposób prezentacji problemu w postaci kilku rozwiązań z ich plusami i minusami. Blog będę odwiedzał regularnie :]

Dodaj komentarz

Twój adres email nie zostanie opublikowany.