Cas d'utilisation réels d'opérateurs au niveau du bit [fermé]

Quels sont les cas d'utilisation réels des opérateurs binaires suivants?

• ET
• XOR
• NE PAS
• OU
• Décalage gauche / droite

• Champs de bits (drapeaux)
  Ils sont le moyen le plus efficace de représenter quelque chose dont l'état est défini par plusieurs propriétés "oui ou non". Les listes de contrôle d'accès sont un bon exemple; si vous avez disons 4 autorisations discrètes (lecture, écriture, exécution, changement de politique), il est préférable de le stocker dans 1 octet plutôt que de le gaspiller 4. Ceux-ci peuvent être mappés à des types d'énumération dans de nombreuses langues pour plus de commodité.

• La communication sur les ports / sockets
  implique toujours des sommes de contrôle, la parité, des bits d'arrêt, des algorithmes de contrôle de flux, etc., qui dépendent généralement des valeurs logiques des octets individuels par opposition aux valeurs numériques, car le support peut uniquement être capable de transmettre un bit à un temps.

• Compression, chiffrement
  Les deux dépendent fortement des algorithmes au niveau du bit. Regardez l' algorithme de dégonflage pour un exemple - tout est en bits, pas en octets.

• Machines à états finis
  Je parle principalement du type de matériel embarqué, même si elles se trouvent également dans les logiciels. Ceux - ci sont combinatoires dans la nature - ils pourraient littéralement être obtenir « compilé » vers le bas à un tas de portes logiques, donc ils doivent être exprimés en AND, OR, NOT, etc.

• Graphiques Il n'y a guère assez d'espace ici pour entrer dans tous les domaines où ces opérateurs sont utilisés dans la programmation graphique. XOR(ou ^) est particulièrement intéressant ici car appliquer la même entrée une deuxième fois annulera la première. Les anciennes interfaces graphiques s'en servaient pour la mise en évidence de la sélection et d'autres superpositions, afin d'éliminer le besoin de redessiner coûteux. Ils sont toujours utiles dans les protocoles graphiques lents (c'est-à-dire le bureau à distance).

Ce ne sont que les premiers exemples que j'ai trouvés - ce n'est pas une liste exhaustive.

Est-ce étrange?

(value & 0x1) > 0

Est-il divisible par deux (pair)?

(value & 0x1) == 0

Voici quelques idiomes courants traitant des drapeaux stockés sous forme de bits individuels.

enum CDRIndicators {
  Local = 1 << 0,
  External = 1 << 1,
  CallerIDMissing = 1 << 2,
  Chargeable = 1 << 3
};

unsigned int flags = 0;

Réglez le drapeau facturable:

flags |= Chargeable;

Effacer l'indicateur CallerIDMissing:

flags &= ~CallerIDMissing;

Testez si CallerIDMissing et Chargeable sont définis:

if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {

}

J'ai utilisé des opérations au niveau du bit dans la mise en œuvre d'un modèle de sécurité pour un CMS. Il y avait des pages auxquelles les utilisateurs pouvaient accéder s'ils faisaient partie des groupes appropriés. Un utilisateur peut être dans plusieurs groupes, nous avons donc dû vérifier s'il y avait une intersection entre les groupes d'utilisateurs et les groupes de pages. Nous avons donc attribué à chaque groupe un identifiant unique de puissance de 2, par exemple:

Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100

Nous OU ensemble ces valeurs, et stockons la valeur (comme un seul entier) avec la page. Par exemple, si une page est accessible aux groupes A et B, nous stockons la valeur 3 (qui en binaire est 00000011) comme contrôle d'accès aux pages. De la même manière, nous stockons une valeur d'identificateurs de groupe OR avec un utilisateur pour représenter les groupes dans lesquels ils se trouvent.

Donc, pour vérifier si un utilisateur donné peut accéder à une page donnée, il vous suffit de ET ensemble les valeurs et de vérifier si la valeur est non nulle. C'est très rapide car cette vérification est implémentée en une seule instruction, sans boucle, sans aller-retour dans la base de données.

La programmation de bas niveau est un bon exemple. Vous pouvez, par exemple, avoir besoin d'écrire un bit spécifique dans un registre mappé en mémoire pour faire en sorte qu'un matériel fasse ce que vous voulez:

volatile uint32_t *register = (volatile uint32_t *)0x87000000;
uint32_t          value;
uint32_t          set_bit   = 0x00010000;
uint32_t          clear_bit = 0x00001000;

value = *register;            // get current value from the register
value = value & ~clear_bit;   // clear a bit
value = value | set_bit;      // set a bit
*register = value;            // write it back to the register

De plus, htonl()et htons()sont implémentés à l'aide des opérateurs &et |(sur les machines dont l' endianité (ordre des octets) ne correspond pas à l'ordre du réseau):

#define htons(a) ((((a) & 0xff00) >> 8) | \
                  (((a) & 0x00ff) << 8))

#define htonl(a) ((((a) & 0xff000000) >> 24) | \
                  (((a) & 0x00ff0000) >>  8) | \
                  (((a) & 0x0000ff00) <<  8) | \
                  (((a) & 0x000000ff) << 24))

Je les utilise pour obtenir des valeurs RVB (A) à partir de valeurs de couleurs emballées, par exemple.

Quand j'ai un tas de drapeaux booléens, j'aime les stocker tous dans un int.

Je les fais sortir en utilisant ET au niveau du bit. Par exemple:

int flags;
if (flags & 0x10) {
  // Turn this feature on.
}

if (flags & 0x08) {
  // Turn a second feature on.
}

etc.

& = ET:
Masque des bits spécifiques.
Vous définissez les bits spécifiques qui doivent être affichés ou non affichés. 0x0 & x effacera tous les bits d'un octet tandis que 0xFF ne changera pas x. 0x0F affichera les bits dans le quartet inférieur.

Conversion:
pour convertir des variables plus courtes en variables plus longues avec une identité binaire, il est nécessaire d'ajuster les bits car -1 dans un entier est 0xFFFFFFFF tandis que -1 dans un long est 0xFFFFFFFFFFFFFFFF. Pour préserver l'identité, vous appliquez un masque après la conversion.

| = OU
Définissez les bits. Les bits seront définis indépendamment s'ils sont déjà définis. De nombreuses infrastructures de données (champs binaires) ont des indicateurs comme IS_HSET = 0, IS_VSET = 1 qui peuvent être définis indépendamment. Pour définir les indicateurs, vous appliquez IS_HSET | IS_VSET (en C et en assemblage, c'est très pratique à lire)

^ = XOR
Recherche des bits identiques ou différents.

~ = PAS
Flip bits.

On peut montrer que toutes les opérations binaires locales possibles peuvent être mises en œuvre par ces opérations. Donc, si vous le souhaitez, vous pouvez implémenter une instruction ADD uniquement par des opérations binaires.

Quelques merveilleux hacks:

http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html

Le chiffrement est toutes les opérations au niveau du bit.

Vous pouvez les utiliser comme un moyen rapide et sale de hacher des données.

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;

Je viens d'utiliser bitwise-XOR ( ^) il y a environ trois minutes pour calculer une somme de contrôle pour la communication série avec un automate ...

Bitwise & est utilisé pour masquer / extraire une certaine partie d'un octet.

Variable de 1 octet

 01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
 --------
 00000010

En particulier, l'opérateur de décalage (<< >>) est souvent utilisé pour les calculs.

Ceci est un exemple pour lire les couleurs d'une image bitmap au format octet

byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */

//To only have red
byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */

//Now, we only want red colour
redColour = (redColour >> 24) & 0xFF;  /* This now returns a red colour between 0x00 and 0xFF.

J'espère que ces petits exemples vous aideront ...

Dans le monde abstrait de la langue moderne d'aujourd'hui, pas trop. L'entrée-sortie de fichier est une tâche facile qui me vient à l'esprit, bien qu'elle consiste à exercer des opérations au niveau du bit sur quelque chose déjà implémenté et n'implémente pas quelque chose qui utilise des opérations au niveau du bit. Néanmoins, à titre d'exemple simple, ce code illustre la suppression de l'attribut en lecture seule sur un fichier (afin qu'il puisse être utilisé avec un nouveau FileStream spécifiant FileMode.Create) en c #:

//Hidden files posses some extra attibutes that make the FileStream throw an exception
//even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it!
if(File.Exists(targetName))
{
    FileAttributes attributes = File.GetAttributes(targetName);

    if ((attributes & FileAttributes.ReadOnly) == FileAttributes.ReadOnly)
        File.SetAttributes(targetName, attributes & (~FileAttributes.ReadOnly));

    File.Delete(targetName);
}

En ce qui concerne les implémentations personnalisées, voici un exemple récent: j'ai créé un "centre de messages" pour envoyer des messages sécurisés d'une installation de notre application distribuée à une autre. Fondamentalement, il est analogue au courrier électronique, avec Inbox, Outbox, Sent, etc., mais il a également une livraison garantie avec des accusés de lecture, il existe donc des sous-dossiers supplémentaires au-delà de "boîte de réception" et "envoyé". Ce que cela signifiait était une obligation pour moi de définir de manière générique ce qui est "dans la boîte de réception" ou ce qui est "dans le dossier envoyé". Du dossier envoyé, j'ai besoin de savoir ce qui est lu et ce qui n'est pas lu. De ce qui n'est pas lu, j'ai besoin de savoir ce qui est reçu et ce qui ne l'est pas. J'utilise ces informations pour créer une clause where dynamique qui filtre une source de données locale et affiche les informations appropriées.

Voici comment l'énumération est constituée:

    public enum MemoView :int
    {
        InboundMemos = 1,                   //     0000 0001
        InboundMemosForMyOrders = 3,        //     0000 0011
        SentMemosAll = 16,                  //     0001 0000
        SentMemosNotReceived = 48,          //     0011
        SentMemosReceivedNotRead = 80,      //     0101
        SentMemosRead = 144,                //     1001
        Outbox = 272,                       //0001 0001 0000
        OutBoxErrors = 784                  //0011 0001 0000
    }

Voyez-vous ce que cela fait? En anding (&) avec la valeur d'énumération "Inbox", InboundMemos, je sais que InboundMemosForMyOrders est dans la boîte de réception.

Voici une version réduite de la méthode qui crée et renvoie le filtre qui définit une vue pour le dossier actuellement sélectionné:

    private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
    {
        string filter = string.Empty;
        if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
        {
            filter = "<inbox filter conditions>";

            if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
            {
                filter += "<my memo filter conditions>";
            }
        }
        else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
        {
            //all sent items have originating system = to local
            filter = "<memos leaving current system>";

            if((view & MemoView.Outbox) == MemoView.Outbox)
            {
                ...
            }
            else
            {
                //sent sub folders
                filter += "<all sent items>";

                if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived)
                {
                    if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead)
                    {
                        filter += "<not received and not read conditions>";
                    }
                    else
                        filter += "<received and not read conditions>";
                }
            }
        }

        return filter;
    }

Extrêmement simple, mais une implémentation soignée à un niveau d'abstraction qui ne nécessite généralement pas d'opérations au niveau du bit.

L'encodage Base64 en est un exemple. Le codage Base64 est utilisé pour représenter les données binaires sous forme de caractères imprimables pour l'envoi via des systèmes de messagerie (et à d'autres fins). Le codage Base64 convertit une série d'octets 8 bits en index de recherche de caractères 6 bits. Les opérations sur les bits, le décalage et le «ou», le «pas» sont très utiles pour implémenter les opérations sur les bits nécessaires au codage et au décodage Base64.

Bien sûr, ce n'est qu'un des innombrables exemples.

Je suis surpris que personne n'ait choisi la réponse évidente pour l'ère d'Internet. Calcul des adresses réseau valides pour un sous-réseau.

http://www.topwebhosts.org/tools/netmask.php

Les opérations au niveau du bit sont généralement plus rapides que la multiplication / division. Donc, si vous devez multiplier une variable x par 9, vous ferez ce x<<3 + xqui serait quelques cycles plus rapide que x*9. Si ce code se trouve dans un ISR, vous économiserez du temps de réponse.

De même, si vous souhaitez utiliser un tableau comme file d'attente circulaire, il serait plus rapide (et plus élégant) de gérer les contrôles de bouclage avec des opérations au niveau du bit. (la taille de votre baie doit être une puissance de 2). Par exemple:, vous pouvez utiliser à la tail = ((tail & MASK) + 1)place de tail = ((tail +1) < size) ? tail+1 : 0, si vous souhaitez insérer / supprimer.

De plus, si vous souhaitez qu'un indicateur d'erreur contienne plusieurs codes d'erreur, chaque bit peut contenir une valeur distincte. Vous pouvez ET avec chaque code d'erreur individuel comme vérification. Ceci est utilisé dans les codes d'erreur Unix.

Un bitmap à n bits peut également être une structure de données vraiment cool et compacte. Si vous souhaitez allouer un pool de ressources de taille n, nous pouvons utiliser un n-bits pour représenter l'état actuel.

Personne ne semble avoir mentionné les mathématiques à virgule fixe.

(Ouais, je suis vieux, ok?)

Un nombre est-il xune puissance de 2? (Utile par exemple dans les algorithmes où un compteur est incrémenté et où une action ne doit être effectuée que le nombre de fois logarithmique)

(x & (x - 1)) == 0

Quel est le bit le plus élevé d'un entier x? (Ceci peut par exemple être utilisé pour trouver la puissance minimale de 2 supérieure à x)

x |= (x >>  1);
x |= (x >>  2);
x |= (x >>  4);
x |= (x >>  8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift

Quel est le 1bit le plus bas d'un entier x? (Aide à trouver le nombre de fois divisible par 2.)

x & -x

Les opérateurs au niveau du bit sont utiles pour boucler des tableaux dont la longueur est une puissance de 2. Comme beaucoup de personnes l'ont mentionné, les opérateurs au niveau du bit sont extrêmement utiles et sont utilisés dans les indicateurs , les graphiques , les réseaux , le cryptage . Non seulement cela, mais ils sont extrêmement rapides. Mon utilisation préférée personnelle est de boucler un tableau sans conditions . Supposons que vous ayez un tableau basé sur un indice zéro (par exemple, l'indice du premier élément est 0) et que vous ayez besoin de le boucler indéfiniment. Par indéfiniment, je veux dire passer du premier élément au dernier et revenir au premier. Une façon de mettre en œuvre ceci est:

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    if (i >= arr.length) 
        i = 0;
}

C'est l'approche la plus simple, si vous souhaitez éviter l' instruction if , vous pouvez utiliser l' approche module comme ceci:

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    i = i % arr.length;
}

L'inconvénient de ces deux méthodes est que l'opérateur de module est coûteux, car il recherche un reste après la division entière. Et la première méthode exécute une instruction if à chaque itération. Avec l'opérateur au niveau du bit, cependant, si la longueur de votre tableau est une puissance de 2, vous pouvez facilement générer une séquence comme 0 .. length - 1en utilisant l' &opérateur (au niveau du bit et) comme tel i & length. Donc, sachant cela, le code d'en haut devient

int[] arr = new int[8];
int i = 0;
while (true){
    print(arr[i]);
    i = i + 1;
    i = i & (arr.length - 1);
}

Voici comment cela fonctionne. Au format binaire , chaque nombre dont la puissance de 2 est soustraite de 1 est exprimé uniquement avec des nombres. Par exemple, 3 en binaire est 11, 7 est 111, 15 est 1111et ainsi de suite, vous avez l'idée. Maintenant, que se passe-t-il si vous &n'importe quel nombre contre un nombre composé uniquement de ceux en binaire? Disons que nous faisons ceci:

num & 7;

Si numest plus petit ou égal à 7, le résultat sera numparce que chaque bit &avec 1 est lui-même. Si numest plus grand que 7, pendant l' &opération, l'ordinateur considérera les zéros de tête de 7 qui, bien sûr, resteront comme des zéros après l' &opération, seule la partie arrière restera. Comme en 9 & 7binaire ça ressemblera

1001 & 0111

le résultat sera 0001 qui est 1 en décimal et adresse le deuxième élément du tableau.

Je les utilise pour les options de sélection multiple, de cette façon je ne stocke qu'une seule valeur au lieu de 10 ou plus

il peut également être pratique dans un modèle relationnel sql, disons que vous avez les tableaux suivants: BlogEntry, BlogCategory

traditionnellement, vous pouvez créer une relation nn entre eux à l'aide d'une table BlogEntryCategory ou lorsqu'il n'y a pas beaucoup d'enregistrements BlogCategory, vous pouvez utiliser une valeur dans BlogEntry pour créer un lien vers plusieurs enregistrements BlogCategory comme vous le feriez avec des énumérations marquées, dans la plupart des SGBDR, il existe également un opérateur très rapide pour sélectionner sur cette colonne "marquée" ...

Lorsque vous souhaitez uniquement modifier certains bits des sorties d'un microcontrôleur, mais que le registre dans lequel écrire est un octet, vous faites quelque chose comme ceci (pseudocode):

char newOut = OutRegister & 0b00011111 //clear 3 msb's
newOut = newOut | 0b10100000 //write '101' to the 3 msb's
OutRegister = newOut //Update Outputs

Bien sûr, de nombreux microcontrôleurs vous permettent de changer chaque bit individuellement ...

Si jamais vous voulez calculer votre nombre mod (%) une certaine puissance de 2, vous pouvez utiliser yourNumber & 2^N-1, qui dans ce cas est le même que yourNumber % 2^N.

number % 16 = number & 15;
number % 128 = number & 127;

C'est probablement seulement utile étant une alternative au fonctionnement du module avec un très gros dividende qui est 2 ^ N ... Mais même alors, son augmentation de vitesse par rapport au fonctionnement du module est négligeable dans mon test sur .NET 2.0. Je soupçonne que les compilateurs modernes effectuent déjà des optimisations comme celle-ci. Quelqu'un en sait-il plus?

Je les ai vus utilisés dans des systèmes de contrôle d'accès basés sur les rôles.

Il y a une utilisation réelle dans ma question ici -
Répondre à la première notification WM_KEYDOWN uniquement?

Lors de la consommation d'un message WM_KEYDOWN dans les fenêtres, le bit 30 de l'api C spécifie l'état de clé précédent. La valeur est 1 si la clé est enfoncée avant l'envoi du message, ou elle est nulle si la clé est enfoncée

Ils sont principalement utilisés pour les opérations au niveau du bit (surprise). Voici quelques exemples concrets trouvés dans la base de code PHP.

Encodage de caractère:

if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {

Structures de données:

ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;

Pilotes de base de données:

dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);

Implémentation du compilateur:

opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;

Chaque fois que j'ai commencé la programmation en C, j'ai compris les tables de vérité et tout ça, mais tout n'a pas cliqué sur la façon de l'utiliser réellement jusqu'à ce que je lise cet article http://www.gamedev.net/reference/articles/article1563.asp (qui donne des exemples concrets)

Je ne pense pas que cela compte comme bit à bit, mais le tableau de ruby ​​définit les opérations de set via les opérateurs bit à bit entiers normaux. Alors [1,2,4] & [1,2,3] # => [1,2]. De même pour a ^ b #=> set differenceet a | b #=> union.

La solution linéaire Tower Of Hanoi utilise des opérations au niveau du bit pour résoudre le problème.

public static void linear(char start, char temp, char end, int discs)
{
    int from,to;
    for (int i = 1; i < (1 << discs); i++) {
        from = (i & i-1) % 3;
        to = ((i | i-1) + 1) % 3;
        System.out.println(from+" => "+to);
    }
}

L'explication de cette solution se trouve ici