Notatnik techniczny

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.

Policz jedynki w zapisie binarnym liczby

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

using namespace std;
using uint = unsigned int;

template<typename T>
uint PoliczUstawioneBity( T arg ) noexcept
{
..........
}

Przykładowe wyniki

Argument Wynik
0 0
1 1
2 1
3 2
255 8
325423 13

Rozwiązanie z tablicą bitów

#include <bitset>
template<typename T>
uint PoliczUstawioneBity_1( T arg ) noexcept
{
    const uint rozmiarBity = 8 * sizeof(arg);
    auto bits = bitset< rozmiarBity >(arg);
    uint result = 0;
    for(int i = 0; i< rozmiarBity; ++i)
        result += bits[i];
    return result;
}

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.

template<typename T>
uint PoliczUstawioneBity_2( T arg ) noexcept
{
    int result = 0;
    while ( arg != 0 )
    {
        result += arg % 2;
        arg = arg / 2;
    }
    return result;
}

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

template<typename T>
uint PoliczUstawioneBity_3( T arg ) noexcept
{
    int result = 0;
    for(int i = 0; i< 8 * sizeof(arg); ++i)
    {
        result += arg & 0x1;
        arg = arg >> 1;
    }
    return result;
}

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

template<typename T>
uint PoliczUstawioneBity_4( T arg ) noexcept
{
    static const unsigned char pre_computed_values[] = {
            0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,
            3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,
            3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,
            6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,
            3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,
            5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,
            6,7,5,6,6,7,6,7,7,8};
 
    int result = 0;
    while ( arg != 0 )
    {
        result += pre_computed_values[arg & 0xFF];
        arg = arg >> 8;
    }
    return result;
}

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