opérations sur le vecteur de bits

Question

Quelle est la meilleure façon d'effectuer des opérations de manipulation de bits sur vector<bool>?

que je comprends, vector<bool> est une spécialisation qui utilise un bit par booléenne. J'ai choisi vector<bool> pour des raisons d'économie de mémoire. Je sais qu'il ya des problèmes avec vector<bool> mais pour mes besoins, il apropriate de.

- ce qui est la façon la plus performante de aplying opérations de bits pour de tels vecteurs entiers

si je le fais dans une boucle et la lecture chaque seule bool et le stocker en arrière, la façon dont je le comprends beaucoup plus les opérations sont effectuées à l'intérieur afin d'accéder aux valeurs réelles.

merci!

Answer 1

Si le nombre de bits sont fixés au moment de la compilation, vous seriez beaucoup mieux en utilisant std::bitset

Dans le cas contraire, (nombre de bits varie à l'exécution), alors vous devriez voir et pouvez utiliser boost::dynamic_bitset )

Dans ces deux, il est extrêmement facile de faire toutes les opérations de manipulation de bits.

Answer 2

Ignorant le titre de votre question, permet de répondre cette question, au lieu:

  

Quelle est la meilleure façon d'effectuer des opérations sur le vecteur de manipulation de bits?

La meilleure façon est de définir votre vecteur vector<unsigned char> (ou vector<uint32_t>, ou selon un autre type entier que vous choisissez), et faire vos opérations au niveau du bit comment vous le feriez normalement pour un tableau d'entiers non signés. Les choses seront beaucoup plus rapide de cette façon, et il n'y aura pas de mécanisme caché.

Vous pouvez utiliser la division (ou les opérateurs au niveau du bit, si vous êtes habile) pour résoudre l'index de tableau vous devez utiliser contre, et boucles pour appliquer des opérations au niveau du bit plus grand qu'un seul élément.

Voici une question connexe: Bit twiddling un grand nombre de bits dans C

Vous essentiellement accomplirez ces mêmes opérations, si et quand vous décidez d'envelopper vector<unsigned some-int-type> avec vos propres opérateurs.

Answer 3

Je lis ces deux réponses, mais je voulais juste une solution rapide, et mis en œuvre quelque chose d'horrible.

Vous pouvez faire les opérateurs de travailler sur vector<bool> au niveau du bit, mais le code doit être spécialisé pour l'implémentation C ++ de bibliothèque standard ou revenir à la forme lente. Voici mon operator| pour GNU libstdc ++ - v3:

std::vector<bool> operator|(std::vector<bool> A, const std::vector<bool>& B)
{
    if (A.size() != B.size())
        throw std::invalid_argument("differently sized bitwise operands");

    std::vector<bool>::iterator itA = A.begin();
    std::vector<bool>::const_iterator itB = B.begin();

    // c++ implementation-specific
    while (itA < A.end())
        *(itA._M_p ++) |= *(itB._M_p ++); // word-at-a-time bitwise operation

    return A;
}

Ceci est bien sûr assez mauvais. Quelqu'un met à jour GCC, les nouvelles choses stocke la version différemment, et vos pauses de code pour aucune raison apparente.

Answer 4

Celui-ci devrait fonctionner aussi.

std::vector<bool> v3(v1.size());
std::transform(v1.begin(), v1.end(), 
               v2.begin(), v3.begin(), std::logical_and<bool>());