À quoi servent les opérateurs de bits? [fermé]

Les langages de programmation viennent souvent avec différents opérateurs de bits (par exemple décalage gauche et droite au niveau du bit, AND au niveau du bit, OR, XOR ...). Celles-ci ne sont cependant pas très utilisées, ou du moins telle a été mon expérience. Ils sont parfois utilisés dans des défis de programmation ou des questions d'entrevue, ou la solution pourrait les nécessiter, par exemple:

• Sans utiliser d'opérateur d'égalité, créez une fonction qui renvoie truelorsque deux valeurs sont égales
• Sans utiliser une troisième variable, permutez la valeur de deux variables

Ceux-ci, encore une fois, ont probablement peu d'utilisations réelles . Je suppose qu'ils devraient être plus rapides car ils manipulent directement la mémoire à un faible niveau.

Pourquoi en trouve-t-on dans la plupart des langages de programmation? Des cas d'utilisation réels?

Non, ils ont de nombreuses applications réelles et sont des opérations fondamentales sur les ordinateurs.

Ils sont utilisés pour

• Jongler avec des blocs d'octets qui ne correspondent pas aux types de données des langages de programmation
• Basculer l'encodage d'avant en arrière du gros au petit endian.
• Emballage de 4 données 6 bits en 3 octets pour une connexion série ou USB
• De nombreux formats d'image ont des quantités de bits différentes attribuées à chaque canal de couleur.
• Tout ce qui implique des broches IO dans des applications embarquées
• La compression des données, qui souvent n'a pas de données adaptées à de belles limites 8 bits. \
• Algorithmes de hachage, CRC ou autres contrôles d'intégrité des données.
• Chiffrement
• Génération de nombres aléatoires
• Raid 5 utilise XOR au niveau du bit entre les volumes pour calculer la parité.
• Des tonnes de plus

En fait, logiquement, toutes les opérations sur un ordinateur se résument finalement à des combinaisons de ces opérations au niveau du bit de bas niveau, qui ont lieu dans les portes électriques du processeur.

Parce que ce sont des opérations fondamentales.

Par la même ligne de pensée, vous pourriez faire valoir que l' addition a peu d'utilisations réelles, car elle peut être remplacée complètement par la soustraction (et la négation) et la multiplication. Mais nous gardons l'addition car c'est une opération fondamentale.

Et ne pensez pas un instant que le simple fait que vous n'ayez pas vu un grand besoin d'opérations au niveau du bit ne signifie pas qu'elles ne sont pas utilisées très souvent. En effet, j'ai utilisé des opérations au niveau du bit dans presque tous les langages que j'ai utilisés pour des choses comme le masquage de bits.

Du haut de ma tête, j'ai utilisé des opérations au niveau du bit pour le traitement d'image, les champs de bits et les indicateurs, le traitement de texte (par exemple, tous les caractères d'une classe particulière partagent souvent un modèle de bits commun), l'encodage et le décodage de données sérialisées, le décodage de VM ou CPU opcodes, etc. Sans opérations au niveau du bit, la plupart de ces tâches nécessiteraient des opérations beaucoup plus complexes pour effectuer la tâche de manière moins fiable ou avec une meilleure lisibilité.

Par exemple:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

Le décodage des instructions CPU pour les CPU de type RISC (comme lors de l'émulation d'une autre plate-forme) nécessite d'extraire des parties d'une grande valeur comme ci-dessus. Parfois, effectuer ces opérations avec multiplication et division et modulo, etc., peut être jusqu'à dix fois plus lent que les opérations binaires équivalentes.

Un exemple typique consiste à extraire les couleurs individuelles d'une valeur RVB 24 bits et inversement.

MODIFIER: depuis http://www.docjar.com/html/api/java/awt/Color.java.html

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );

Voici un exemple du monde réel que vous trouverez dans Quake 3, Quake 4. Doom III. Tous ces jeux qui utilisaient le moteur Q3 .

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(Pour comprendre ce code, vous devez comprendre comment les nombres à virgule flottante sont stockés, je ne peux certainement pas développer cela)

En termes d'utilisation, à moins que vous ne soyez dans des domaines qui nécessitent un décalage de bits tels que la mise en réseau ou les graphiques, vous pouvez trouver leur objectif légèrement académique. Mais toujours intéressant (du moins pour moi).

Le décalage est plus rapide que la multiplication ou la division par une puissance de deux. Par exemple, a << = 2 multiplie a par 4. A l'inverse, a >> = 2 divise a par quatre. On peut également bit-bang des données vers un périphérique en utilisant les opérateurs bit par bit. Par exemple, nous pouvons envoyer N flux de données série à partir d'un port N broches en utilisant les opérations shift, xor et "and" à l'intérieur de N boucles. Tout ce qui peut être accompli en logique numérique peut également être accompli sur le logiciel et vice versa.

Il y a très longtemps, les opérateurs de bits étaient utiles. Aujourd'hui, ils le sont moins. Oh, ils ne sont pas entièrement inutiles, mais cela fait longtemps que je n'en ai pas vu un qui aurait dû être utilisé.

En 1977, j'étais programmeur en langage assembleur. J'étais convaincu que l'assembleur était la seule vraie langue. Je suis certain que la langue comme Pascal étaient pour weenies universitaires qui n'a jamais eu à faire quoi que ce soit vrai fait.

J'ai ensuite lu "The C Programming Language" de Kernighan et Ritchie. Cela a complètement changé d'avis. La raison? Il y avait des opérateurs peu! Il était un langage d'assemblage! Il avait juste une syntaxe différente.

À l'époque, je ne pouvais pas imaginer écrire du code sans ands, ors, shifts et rotates. De nos jours, je ne les utilise presque jamais.

Donc, la réponse courte à votre question est: "Rien". Mais ce n'est pas tout à fait juste. Donc, la réponse la plus longue est: "Surtout rien."

Chiffrement

Je suggère de jeter un coup d'œil à un très petit extrait de l' algorithme de cryptage DES :

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);

Beaucoup de bonnes réponses, donc je ne répéterai pas ces utilisations.

Je les utilise beaucoup dans le code managé (C # / .Net), et cela n'a rien à voir avec des algorithmes d'économie d'espace, de hautes performances ou de décalage de bits intelligent. Parfois, une logique est tout simplement bien adaptée au stockage de données de cette manière. Je les utilise souvent lorsque j'ai une énumération, mais les instances peuvent simultanément prendre plusieurs valeurs de cette énumération. Je ne peux pas poster un exemple de code de travail, mais un rapide google pour "Flags enum" ("Flags" est la manière C # de définir une énumération à utiliser au niveau du bit) donne ce bel exemple: http: // www.dotnetperls.com/enum-flags .

Il y a aussi le calcul parallèle en bits. Si vos données ne sont que 1 et 0, vous pouvez en regrouper 64 dans un mot long non signé et obtenir des opérations parallèles 64 voies. Les informations génétiques sont sur deux bits (représentant le codage AGCT de l'ADN), et si vous pouvez effectuer les différents calculs de façon parallèle, vous pouvez faire beaucoup plus que si vous ne le faites pas. Sans parler de la densité des données en mémoire - si la mémoire, ou la capacité du disque, ou la bande passante des communications est limitée implique que la compression / décompression doit être envisagée. Même les entiers à faible précision, qui apparaissent dans des domaines tels que le traitement d'image, peuvent tirer parti du calcul parallèle délicat. C'est tout un art en soi.

Pourquoi les trouve-t-on?

Eh bien, c'est probablement parce qu'ils correspondent aux instructions de montage et parfois ils sont juste utiles pour des choses dans des langages de niveau supérieur. La même chose s'applique au redouté GOTOqui correspond à l' JMPinstruction d'assemblage.

Quelles sont leurs utilisations?

Vraiment, il y a trop d'utilisations à nommer, je vais donc donner un usage récent, bien que très localisé. Je travaille beaucoup avec l'assemblage 6502 et je travaillais sur une petite application qui convertit les adresses de mémoire, les valeurs, compare les valeurs, etc. en codes qui peuvent être utilisés pour l'appareil GameGenie (Fondamentalement, une application de triche pour la NES). Les codes sont créés par une manipulation de bits.

De nos jours, de nombreux programmeurs sont habitués aux ordinateurs avec une mémoire quasi infinie.

Mais certains utilisent toujours de minuscules microcontrôleurs où chaque bit compte (lorsque vous n'avez que 1 Ko ou moins de RAM par exemple), et les opérateurs au niveau du bit permettent à un programmeur d'utiliser ces bits un à la fois au lieu de gaspiller une programmation beaucoup plus grande entité d'abstraction qui pourrait être nécessaire pour conserver un état requis par l'algorithme. L'E / S sur ces appareils peut également nécessiter une lecture ou un contrôle au niveau du bit.

Le «monde réel» possède bien plus de ces minuscules microcontrôleurs que des serveurs ou des PC.

Pour les types CS théoriques purs, les machines Turing sont toutes des bits d'état.

Encore une des nombreuses utilisations possibles des opérateurs au niveau du bit ...

Les opérateurs au niveau du bit peuvent également aider à rendre votre code plus lisible. Considérez la déclaration de fonction suivante ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

Il est très facile d'oublier quel paramètre booléen signifie quoi lors de l'écriture ou même de la lecture du code. Il est également facile de perdre la trace de votre comptage. Une telle routine peut être nettoyée.

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

Avec des noms d'indicateur plus descriptifs, il devient beaucoup plus lisible.

Si vous savez quelque chose sur Unicode , vous connaissez probablement UTF-8. Il utilise un tas de tests de bits, de décalages et de masques pour compresser le point de code de 20 bits en 1 à 4 octets.

Je ne les utilise pas souvent mais parfois ils sont utiles. La manipulation de l'énum vient à l'esprit.

Exemple:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...

Je ne sais pas si cette utilisation a encore été notée:

Je vois OU beaucoup lorsque je travaille avec le code source illumos (openSolaris) pour réduire plusieurs valeurs de retour à 0 ou 1, par exemple

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;