C / C ++ Array Bit ou vecteur binaire

Question

J'apprends C / C ++ programmation et ont rencontré l'utilisation des « tableaux de bits » ou « Bit vecteurs ». Je ne suis pas en mesure de comprendre leur but? voici mes doutes -

1. Sont-ils utilisés comme indicateurs booléens?
2. Peut-on utiliser à la place des tableaux de int? (Plus de mémoire bien sûr, mais ..)
3. Quel est ce concept de Bit-Masking?
4. Si le bit-masquage est des opérations simples de bits pour obtenir un drapeau approprié, comment faire un programme pour eux? est-il pas difficile de faire cette opération dans la tête pour voir ce que le drapeau serait, par opposition à des nombres décimaux?

Je cherche des applications, afin que je puisse mieux comprendre. pour exemple -

Q. vous donne un fichier contenant des nombres entiers dans la gamme (1 à 1 million). Il y a des doublons et donc quelques chiffres manquent. Trouvez le moyen le plus rapide de trouver manquant chiffres?

Pour la question ci-dessus, j'ai lu des solutions me disant d'utiliser des tableaux de bits. Comment peut-on stocker chaque entier un peu?

Answer 1

Je pense que vous avez vous-même confus entre les tableaux et les nombres, plus précisément ce que cela signifie pour manipuler des nombres binaires.

Je vais à ce sujet par exemple. Disons que vous avez un certain nombre de messages d'erreur et que vous voulez les retourner dans une valeur de retour d'une fonction. Maintenant, vous pouvez étiqueter vos erreurs 1,2,3,4 ... ce qui est logique à votre esprit, mais comment voulez-vous, étant donné qu'un seul numéro, le travail sur les erreurs qui ont eu lieu?

Maintenant, essayez de marquer les erreurs 1,2,4,8,16 ... puissances croissantes de deux, au fond. Pourquoi ce travail? Eh bien, quand vous travaillez base 2 vous manipulez un numéro comme 00000000 où chaque chiffre correspond à une puissance de 2 multipliée par sa position de la droite. Alors disons que les erreurs 1, 4 et 8 se produisent. Eh bien, cela pourrait être représenté comme 00001101. A l'inverse, le premier chiffre = 1 * 2 ^ 0, le troisième chiffre 1 * 2 ^ 2 et le quatrième chiffre 1 * 2 ^ 3. En les ajoutant tout vous donne 13.

Maintenant, nous sommes en mesure de tester si une telle erreur est survenue en appliquant un masque de bits. Par exemple, si vous vouliez travailler si 8 d'erreur est survenue, utilisez la représentation binaire de 8 = 00001000. Maintenant, afin d'extraire ou non cette erreur est survenue, utilisez un binaire et comme ceci:

  00001101
& 00001000
= 00001000

Je suis sûr que vous savez comment une et fonctionne ou peut déduire de ce qui précède -. Chiffres-sage de travail, si deux chiffres sont à la fois 1, le résultat est 1, sinon il est 0

, en C:

int func(...)
{
    int retval = 0;

    if ( sometestthatmeans an error )
    {
        retval += 1;
    }


    if ( sometestthatmeans an error )
    {
        retval += 2;
    }
    return retval
}

int anotherfunc(...)
{
    uint8_t x = func(...)

    /* binary and with 8 and shift 3 plaes to the right
     * so that the resultant expression is either 1 or 0 */
    if ( ( ( x & 0x08 ) >> 3 ) == 1 )
    {
        /* that error occurred */
    }
}

Maintenant, pour les aspects pratiques. Lorsque la mémoire était clairsemée et des protocoles n'a pas le luxe de etc xml bavard, il était courant de délimiter un champ comme autant de bits. Dans ce domaine, vous attribuez différents bits (drapeaux, puissances de 2) à un certain sens et d'appliquer des opérations binaires pour en déduire si elles sont définies, puis actionnez sur ces derniers.

Je dois aussi ajouter que les opérations binaires sont proches en idée de l'électronique sous-jacentes d'un ordinateur. Imaginez si les champs de bits correspondent à la sortie des différents circuits (transport de courant ou non). En utilisant suffisamment de combinaisons desdits circuits, vous faites ... un ordinateur.

Answer 2

en ce qui concerne l'utilisation du tableau de bits:

si vous savez qu'il ya « seulement » 1 million de numéros - vous utilisez un tableau de 1 million de bits. au début tous les bits seront zéro et chaque fois que vous lisez un numéro -. utiliser ce numéro comme index et changer le bit dans cet index pour être l'un (si ce n'est pas déjà)

après avoir lu tous les numéros - les numéros manquants sont les indices des zéros dans le tableau

.

par exemple, si nous avions des chiffres entre 0 - 4 le tableau se présente comme suit au début: 0 0 0 0 0. si on lit les chiffres: 3, 2, 2 le tableau ressemblerait à ceci: lire 3 -> 0 0 0 1 0 lecture 3 (nouveau) -> 0 0 0 1 0: 2 -> 0 0 1 1 0. Vérifiez les indices des zéros: 0,1,4 - ce sont les chiffres manquants

BTW, bien sûr, vous pouvez utiliser des entiers au lieu de bits, mais il peut prendre (en fonction du système) 32 fois la mémoire

Sivan

Answer 3

tableaux binaires ou des vecteurs de bits peuvent être bien comme un tableau de valeurs booléennes . Normalement, une variable booléenne a besoin d'au moins une mémoire d'octet, mais dans un réseau bit / vecteur seul bit est nécessaire. Cela devient très pratique si vous avez beaucoup de ces données afin que vous économiser de la mémoire en général.

Une autre utilisation est si vous avez chiffres qui ne correspondent pas exactement dans les variables standard qui sont 8,16,32 ou 64 bits en taille. On pourrait ce magasin de chemin dans un vecteur binaire de 16 bits d'un nombre qui se compose de quatre bits, un bit qui est égal à 2 et qui est de 10 bits en taille. Normalement, vous devez utiliser 3 variables avec des tailles de 8,8 et 16 bits, vous n'avez donc 50% de stockage gaspillé.

Mais toutes ces utilisations sont très rarement utilisés dans les aplications d'affaires, la viennent à utiliser souvent lorsque les pilotes d'interface par PInvoke / Interop fonctions et faire programmation de bas niveau .

Answer 4

Bit tableaux de vecteurs de bits sont utilisés en tant que mappage de position pour une certaine valeur de bit. Oui il est fondamentalement la même chose comme un tableau de Bool, mais typique de mise en œuvre Bool est un à quatre octets et il utilise trop d'espace.

Nous pouvons stocker la même quantité de données beaucoup plus efficace en utilisant des tableaux de mots et des opérations de masquage binaire et décale pour stocker et les récupérer (moins de mémoire globale utilisée, moins accès à la mémoire, moins défaut de cache, moins swap page de mémoire) . Le code d'accès bits individuels est encore assez simple.

Il y a aussi un certain soutien de champ de bits builtin en langage C (vous écrire des choses comme int i:1; à dire « que consommer un peu »), mais il n'est pas disponible pour les tableaux et vous avez moins de contrôle du résultat global (détails de la mise en œuvre dépend des questions du compilateur et d'alignement).

Voici un moyen possible de répondre à votre question « recherche nombres manquants ». Je fixe int taille 32 bits pour garder les choses simples, mais il pourrait être écrit en utilisant sizeof (int) pour le rendre portable. Et (selon le compilateur et le processeur cible) le code ne pourrait être plus rapide à l'aide >> 5 au lieu de / 32 et & 31 au lieu de % 32, mais qui est juste pour donner l'idée.

#include <stdio.h>
#include <errno.h>
#include <stdint.h>

int main(){
    /* put all numbers from 1 to 1000000 in a file, except 765 and 777777 */
    {
        printf("writing test file\n");
        int x = 0;
        FILE * f = fopen("testfile.txt", "w");
        for (x=0; x < 1000000; ++x){
            if (x == 765 || x == 777760 || x == 777791){
                continue;
            }
            fprintf(f, "%d\n", x);
        }
        fprintf(f, "%d\n", 57768); /* this one is a duplicate */
        fclose(f);
    }

    uint32_t bitarray[1000000 / 32];

    /* read file containing integers in the range [1,1000000] */
    /* any non number is considered as separator */
    /* the goal is to find missing numbers */
    printf("Reading test file\n");
    {
        unsigned int x = 0;
        FILE * f = fopen("testfile.txt", "r");
        while (1 == fscanf(f, " %u",&x)){
            bitarray[x / 32] |= 1 << (x % 32);
        }
        fclose(f);
    }
    /* find missing number in bitarray */
    {
        int x = 0;
        for (x=0; x < (1000000 / 32) ; ++x){
            int n = bitarray[x];
            if (n != (uint32_t)-1){
                printf("Missing number(s) between %d and %d [%x]\n",
                    x * 32, (x+1) * 32, bitarray[x]);
                int b;
                for (b = 0 ; b < 32 ; ++b){
                    if (0 == (n & (1 << b))){
                        printf("missing number is %d\n", x*32+b);
                    }
                }
            }
        }
    }
}

Answer 5

qui est utilisé pour le stockage de drapeaux binaires, ainsi que pour analyser les différents domaines de protocoles binaires, où 1 octet est divisé en un certain nombre de champs de bits. Ceci est largement utilisé, dans des protocoles comme TCP / IP, jusqu'à encodages ASN.1, les paquets OpenPGP, et ainsi de suite.