[C++] Da decimale a binario e viceversa

[utente__medio]

Ciao, ho implementato due funzioni per convertire un intero senza segno in un vector<bool> con una capienza pari al numero di bit del tipo intero considerato, e viceversa:

Codice:

#include <iostream>
#include <bitset>
#include <chrono>
#include <cstdint>
#include <vector>

using namespace std;
using namespace std::chrono;

const uint8_t N = 64;

vector<bool> to_bool(uint64_t n)
{
    vector<bool> b(N);
    for(uint8_t i = N - 1; n; n >>= 1)
    {
        b[i--] = 1 & n;
    }
    return b;
}

uint64_t from_bool(const vector<bool> &b)
{
    uint64_t n = 0;
    uint64_t m = (uint64_t)1 << N - 1;
    for(uint8_t i = 0; m; m >>= 1)
    {
        if(b[i++])
        {
            n |= m;
        }
    }
    return n;
}

int main()
{
    uint64_t n = 123456789987654321;
    //----------------------------------------------------------------------------------
    auto start1 = high_resolution_clock::now();
    for(uint64_t i = 0; i < 5000000; ++i)
    {
        vector<bool> b = to_bool(n);
        n = from_bool(b);
    }
    auto stop1 = high_resolution_clock::now();
    cout << duration_cast<milliseconds>(stop1 - start1).count() << " ms\t\t" << n << endl;
    //----------------------------------------------------------------------------------
    auto start2 = high_resolution_clock::now();
    for(uint64_t i = 0; i < 5000000; ++i)
    {
        bitset<N> bs(n);
        n = bs.to_ullong();
    }
    auto stop2 = high_resolution_clock::now();
    cout << duration_cast<milliseconds>(stop2 - start2).count() << " ms\t\t" << n << endl;
}

Secondo voi va bene o si potrebbe fare di meglio?

Inoltre nel main() ho anche cercato di testare l'efficienza dei bitset nel compiere le stesse operazioni, ma nel lanciare il programma ottengo il seguente output:

Codice:

1519 ms         123456789987654321
0 ms            123456789987654321

Process returned 0 (0x0)   execution time : 1.556 s
Press any key to continue.


Non penso che le operazioni con i bitset siano tanto veloci, forse il comportamento riscontrato è dovuto a qualche ottimizzazione del compilatore che impedisce di richiamare più volte le stesse operazioni?


Infine vorrei approfittarne per chiedere un'altra cosa: è possibile fare in modo che una funzione ritorni un riferimento ad un elemento di un bitset, in modo da poter utilizzare il valore ritornato anche come l-value?
Leggendo la documentazione dei bitset ho capito che l'oggetto ritornato dovrebbe essere un bitset::reference, ma non mi compila.

[vict85]

Non hai scritto codici che convertono in decimale, quella operazione viene fatta dall'operatore <<.

Bitset è ovviamente più rapido, infatti, non fa alcuna operazione. Se ragioni un attimo a come sia implementato bitset<64>, ti renderai costo che sarà qualcosa del tipo:

Codice:

template <>
class bitset<64> {
    unsigned long long value;

public:
    constexpr bitset( unsigned long long val ) noexcept : val(val) {}

// codice che non interessa

    unsigned long long to_ullong() const {
        return value;
    }
}

Certo, è qualcosa di un po' più complesso perché non sarà specializzato per 64 ma sarà generico per un qualche N e to_ullong può generare una eccezione. Ma il compilatore dovrebbe capire in fretta che è sostanzialmente quello che ho scritto io.

A questo punto, quello che è dentro il ciclo diventa:

Codice:

unsigned long long value = n;
n = value;

e quindi il ciclo diventa vuoto e l'intero ciclo viene eliminato. In sostanza, il compilatore non fa alcuna operazione tra start2 e stop2.

[utente__medio]

Non hai scritto codici che convertono in decimale, quella operazione viene fatta dall'operatore <<.

Hai ragione, in effetti poi nel post ho scritto:

ho implementato due funzioni per convertire un intero senza segno in un vector<bool> con una capienza pari al numero di bit del tipo intero considerato, e viceversa

Bitset è ovviamente più rapido, infatti, non fa alcuna operazione...

Capisco, quindi se volessi fare un confronto tra bitset e vector<bool> dovrei basarlo sugli accessi? O non ha proprio senso farlo?

Per quanto riguarda invece l'altro dubbio?

è possibile fare in modo che una funzione ritorni un riferimento ad un elemento di un bitset, in modo da poter utilizzare il valore ritornato anche come l-value?
Leggendo la documentazione dei bitset ho capito che l'oggetto ritornato dovrebbe essere un bitset::reference, ma non mi compila.

[vict85]

Mi aspetto performance paragonabili per operazioni con \(N\) molto grande, per \(N\) piccolo è meglio bitset o usare direttamente un intero della dimensione giusta. L'implementazione interna è verosimilmente molto simile. Non capisco cosa cerchi di ottenere usando questo tipo di oggetti: accedere ad un singolo bit è sempre più lento che leggere tutto l'intero.
Ti consiglio di lasciar perdere le astrazioni di questo tipo e lavorare direttamente con interi. Io li uso a lavoro, ma li uso per quel che sono ideati.

[utente__medio]

Grazie, mi hai chiarito molti dubbi con questo tuo ultimo post!

Per una questione di pura curiosità, se qualcuno potesse chiarire questo mio dubbio gliene sarei grato:

è possibile fare in modo che una funzione ritorni un riferimento ad un elemento di un bitset, in modo da poter utilizzare il valore ritornato anche come l-value?
Leggendo la documentazione dei bitset ho capito che l'oggetto ritornato dovrebbe essere un bitset::reference, ma non mi compila.

[vict85]

Non saprei perché non ti compila, comunque è un bitset<N>::reference. Probabilmente lo usi in un modo in cui non è pensato per essere utilizzato. Il compilatore dovrebbe dirti perché non puoi farlo.