Robert Olechowskinotatnik techniczny

Zadanie:

using namespace std;
using uint = unsigned int;

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

Przykładowe wyniki

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

• 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

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

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

• 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

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

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

• 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

• Bit Twiddling Hacks
• POPCNT