Notatnik techniczny
5 czerwca 2016

Zadanie rekrutacyjne #1

Zadanie do wykonania:

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

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.

#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;
}

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ą operację dzielenia.
  • Zmienna w pamięci jest reprezentowana binarnie, mimo to traktujemy ją jak wartość dziesiętną.

Rozwiązanie z przesuwaniem bitów

Pozbywamy się dzielenia na rzecz znacznie prostszego przesuwania bitów i operacji AND.

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;
}

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;
}

Dzielimy nasz argument funkcji na jedno-bajtowe bloki. Dla takiego bloku o rozmiarze 8 bitów przeliczyliśmy wcześniej ilość ustawionych bitów. 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.

Dalsza lektura